算術基本原理
(由質數分解跳轉過嚟)
質數分解或質因分解(Prime Factorization),又叫整數分解(integer factorization),算法基礎、算術基本原理(Fundamental Theorem of Arithmetic),係數論入面一個基本概念,亦可以喺抽象代數入面應用。
質數分解指嘅係每一個自然數或者整數,都可以寫成一堆質數嘅乘法。
例子:
根據質數分解定理,任何一個大過1嘅正整數,就可以寫成一堆質數嘅乘法,而對應呢個數嘅寫法係獨一無二嘅,即係對於每一個正整數 ,都可以寫成 ,而 都係質數。
證明
編輯存在性
編輯假設最少有一個數 係唔可以被寫成一堆質數嘅乘法。
因為 嘅排序性質,所以係有一個最細既 係唔可以被寫成一堆質數嘅乘法。
如果 係質數,咁 就係寫成一堆質數嘅乘法。
如果 唔係質數,咁要係有一個 符合 。
因為 係最細符合條件:「唔可以被寫成一堆質數嘅乘法」,所以 可以被寫成一堆質數嘅乘法。
但係因為 ,所以 可以被寫成一堆質數嘅乘法。
獨特性
編輯假設 可以質數分解成 ,而 都係質數。
因為 ,所以 。
利用歐幾理得推論,因為 係質數,所以 。
同一個原理,可以得知會有一個 。
所以 ,為咗簡化,會將 寫成 ,所以 。
之後約簡得出, 。
因為 係第一個,即係最細嘅自然數係有兩個唔同嘅質數分解,而 ,所以 同埋 。
加埋 , 根本就唔會存在兩個唔同嘅質數分解。
應用
編輯有無窮咁多質數係 呢個樣。
證明:
假設 係唔同嘅質數,但都係 呢個樣。
考慮 。
明顯任何一個 都係令到 成立。(因為 係質數)
如果另外一個 同時 ,但唔係每一個 都係 嘅樣。(因為 )
因為 係單數,所以一定會有一啲質數符合 係 嘅樣。