算術基本原理

質數分解或質因分解（Prime Factorization），又叫整數分解(integer factorization)，算法基礎、算術基本原理（Fundamental Theorem of Arithmetic），係數論入面一個基本概念，亦可以喺抽象代數入面應用。

質數分解由德國數學家高斯嘅《算術研究》用商餘計算嚟證明咗

質數分解指嘅係每一個自然數或者整數，都可以寫成一堆質數嘅乘法。

證明質數分解成立需要用到質數嘅定義、可除性等工具。

例子：$2016=2\times 2\times 2\times 2\times 2\times 3\times 3\times 7=2^{5}\times 3^{2}\times 7$

根據質數分解定理，任何一個大過1嘅正整數，就可以寫成一堆質數嘅乘法，而對應呢個數嘅寫法係獨一無二嘅，即係對於每一個正整數 $k:k\in \mathbb {N} \setminus \{1\}$，都可以寫成 $k={p_{1}}^{a_{1}}{p_{2}}^{a_{2}}{p_{3}}^{a_{3}}\cdots {p_{n}}^{a_{n}}:\{a_{1},a_{2},a_{3}\cdots a_{n}\}\in \mathbb {N}$，而 $p_{1},p_{2},p_{3},\cdots ,p_{n}$ 都係質數。

證明

存在性

假設最少有一個數$n\in \mathbb {N}$係唔可以被寫成一堆質數嘅乘法。

因為$\mathbb {N}$嘅排序性質，所以係有一個最細既$a\in \mathbb {N}$係唔可以被寫成一堆質數嘅乘法。

如果$a$係質數，咁$a=a$就係寫成一堆質數嘅乘法。

如果$a$唔係質數，咁要係有一個$b,c$符合$a=bc$。

因為$a$係最細符合條件：「唔可以被寫成一堆質數嘅乘法」，所以$b,c$可以被寫成一堆質數嘅乘法。

但係因為$a=bc$，所以$a$可以被寫成一堆質數嘅乘法。

獨特性

假設$a>1\in \mathbb {N}$可以質數分解成$a=p_{1}\cdots p_{m}=q_{1}\cdots q_{n}$，而$p_{i},q_{i}$都係質數。

因為$p_{1}|a$，所以$p_{1}|q_{1}\cdots q_{n}$。

利用歐幾理得推論，因為$p_{1}$係質數，所以$p_{1}|q_{j}$。

同一個原理，可以得知會有一個$q_{j}|p_{1}$。

所以$p_{1}=q_{j}$，為咗簡化，會將$q_{j}$寫成$q_{1}$，所以$p_{1}=q_{1}$。

之後約簡得出，$p_{2}\cdots p_{m}=q_{2}\cdots q_{n}$。

因為$a$係第一個，即係最細嘅自然數係有兩個唔同嘅質數分解，而$p_{2}\cdots p_{m}<a$，所以$m=n$同埋$p_{2}=q_{2}\cdots p_{m}=q_{n}$。

加埋$p_{1}=q_{1}$，$a$根本就唔會存在兩個唔同嘅質數分解。

應用

有無窮咁多質數係$4x-1$呢個樣。

證明：

假設$p_{1},p_{2},\cdots ,p_{n}$係唔同嘅質數，但都係$4x-1$呢個樣。

考慮$N=4p_{1}p_{2}\cdots p_{n}-1$。

明顯任何一個$p_{i}$都係令到$p_{i}\not |N$成立。（因為$p_{i}$係質數）

如果另外一個$p\neq p_{i}$同時$p|N$，但唔係每一個$p$都係$4x+1$嘅樣。（因為$N=4p_{1}p_{2}\cdots p_{n}-1$）

因為$N$係單數，所以一定會有一啲質數符合$p|N$係$4x-1$嘅樣。

睇埋

• 質數
• 最大公因數
• 可除性
• 歐幾理得推論
• 代數基本定理