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