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

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

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

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

例子:

根據質數分解定理,任何一個大過1嘅正整數,就可以寫成一堆質數嘅乘法,而對應呢個數嘅寫法係獨一無二嘅。

證明

存在性

假設最少有一個數 係唔可以被寫成一堆質數嘅乘法。

因為 嘅排序性質,所以係有一個最細既 係唔可以被寫成一堆質數嘅乘法。

如果 係質數,咁 就係寫成一堆質數嘅乘法。

如果 唔係質數,咁要係有一個 符合 

因為 係最細符合條件:「唔可以被寫成一堆質數嘅乘法」,所以 可以被寫成一堆質數嘅乘法。

但係因為 ,所以 可以被寫成一堆質數嘅乘法。

獨特性

假設 可以質數分解成 ,而 都係質數。

因為 ,所以 

利用歐幾理得推論,因為 係質數,所以 

同一個原理,可以得知會有一個 

所以 ,為咗簡化,會將 寫成 ,所以 

之後約簡得出, 

因為 係第一個,即係最細嘅自然數係有兩個唔同嘅質數分解,而 ,所以 同埋 

加埋  根本就唔會存在兩個唔同嘅質數分解。

應用

有無窮咁多質數係 呢個樣。

證明:

假設 係唔同嘅質數,但都係 呢個樣。

考慮 

明顯任何一個 都係令到 成立。(因為 係質數)

如果另外一個 同時 ,但唔係每一個 都係 嘅樣。(因為 

因為 係單數,所以一定會有一啲質數符合  嘅樣。

睇埋