質數分解

出自維基百科,自由嘅百科全書
(由算術基本定理跳轉過嚟)
跳去導覽 跳去搵嘢
質數分解由德國數學家高斯嘅《算術研究》用商餘計算嚟證明咗

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

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

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

例子:

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

證明[編輯]

存在性[編輯]

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

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

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

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

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

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

獨特性[編輯]

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

因為,所以

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

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

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

之後約簡得出,

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

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

應用[編輯]

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

證明:

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

考慮

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

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

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

睇埋[編輯]