這是一系列關(guān)于數(shù)論的介紹性文章，目的在于推廣數(shù)學(xué)知識(shí)，拓展讀者的數(shù)學(xué)思維。至于為什么用圖文而不是視頻？圖文有三個(gè)優(yōu)越性：一是圖文數(shù)據(jù)量小，節(jié)省學(xué)習(xí)時(shí)間；二是有助于個(gè)人主動(dòng)思考；三是文字里的關(guān)鍵字，可以方便讀者查閱相關(guān)資料。

素?cái)?shù)是這樣的整數(shù)，它的(正)因數(shù)僅有1與p。不是素?cái)?shù)的整數(shù)叫做合數(shù)。例如，

素?cái)?shù)是以數(shù)的這樣一種整除性為特征的，也就是說(shuō)，它們是用只能被1和它們自身整除這種性質(zhì)定義的。所以，素?cái)?shù)應(yīng)該具有的與它們所整除的數(shù)有關(guān)聯(lián)的特殊性質(zhì)并不是一目了然的。因此，下述與素?cái)?shù)相關(guān)的論斷既是很重要的，又是非顯而易見的。關(guān)于素?cái)?shù)的下述事實(shí)是重要的，但并非顯而易見。

斷言. 令p是素?cái)?shù)，假設(shè)p整除乘積ab，則p整除a或p整除b(或者p既整除a也整除b)

證明 已知p整除乘積ab。如果p整除a，則證明已完成，所以可假設(shè)p不整除a?，F(xiàn)在考慮gcd(p, a)等于什么。既然它整除p，它就是1或p，它也整除a，由于已假設(shè)p不整除a，所以gcd(p, a)不是p。因此gcd(p, a)必等于1。

應(yīng)用p與a的線性方程定理。線性方程定理指出可以求方程

px + ay = 1

的整數(shù)解x與y。 (注意運(yùn)用事實(shí)gcd(p, a)=1。)現(xiàn)在，方程兩邊同乘以b得

pbx + aby = b.

顯然，p整除pbx。由于p整除ab,，p也整除aby。故p整除和pba + aby，從而p整除b。這就完成了斷言的證明。

斷言指出，如果素?cái)?shù)整除乘積ab，則它必整除其中一個(gè)因數(shù)。注意這是素?cái)?shù)的特殊性質(zhì)，對(duì)合數(shù)則不成立，例如，6整除乘積15·14，但是6既不整除15也不整除14。不難將斷言推廣到超出兩個(gè)因數(shù)的乘積的情形。

定理(素?cái)?shù)整除性質(zhì)) 假設(shè)素?cái)?shù)p整除乘積，則p整除中至少一個(gè)因數(shù)。

證明 如果p整除，則證明完成，否則，應(yīng)用斷言到乘積

得出p必整除的結(jié)論。換句話說(shuō)，應(yīng)用與的斷言。我們已知pl整除ab,所以如果p不整除a，則斷言表明p必整除b。

現(xiàn)在已知p整除，如果p整除，則證明完成。否則，應(yīng)用斷言到乘積得出p必整除的結(jié)論，繼續(xù)這種過(guò)程最終必然求得p整除某個(gè)。

每個(gè)人都“知道”正整數(shù)可以恰好用一種方法分解成素?cái)?shù)的乘積。

定理(算術(shù)基本定理) 每個(gè)整數(shù)可唯一分解成素?cái)?shù)乘積

證明 算術(shù)基本定理實(shí)際上包含兩個(gè)斷言.

斷言1 數(shù)n可以以某種方式分解成素?cái)?shù)乘積.

斷言2 僅有一種這樣的因數(shù)分解(除因數(shù)重排外).

從斷言1開始，我們準(zhǔn)備給出歸納證明。首先證明n=2的斷言，然后證明n=3的斷言，n=4的斷言，等等。我們開始觀察2=2,，3=3與4=22，所以，這些數(shù)的每一個(gè)可表示成素?cái)?shù)的乘積。這就證明了n=2,3,4的斷言1。下面假設(shè)我們已證明了對(duì)于直到N的每個(gè)數(shù)n斷言1成立，這意味著我們已證明了每個(gè)數(shù)n<N可分解成素?cái)?shù)的乘積。現(xiàn)在驗(yàn)證N+1時(shí)的結(jié)論成立。

有兩種可能性。首先，N+1已是素?cái)?shù)，此時(shí)它本身已分解成素?cái)?shù)。其次，N+1是合數(shù)，這表明它可分解成，同時(shí)，已知對(duì)斷言1成立，這是因?yàn)樗鼈兌夹∮诘扔贜。從而與可分解成素?cái)?shù)的乘積，即

將這兩個(gè)乘積乘起來(lái)得

所以,N+1可分解成素?cái)?shù)的乘積。這說(shuō)明對(duì)N+1斷言1成立。

總結(jié)一下，我們已證明如果對(duì)所有小于等于N的數(shù)斷言1成立，則N+1時(shí)斷言1也成立。

下面證明斷言2。這個(gè)斷言也有歸納證明,但我們直接證明它，假設(shè)能將n分解成兩種形式的素?cái)?shù)乘積，即

需要證明當(dāng)重排因數(shù)次序后分解是相同的。首先觀察，所以。本章前面已證的素?cái)?shù)整除性質(zhì)告訴我們必整除中的(至少)一個(gè)。所以如果重排這些可以使得。但是也是素?cái)?shù)，因而它的因數(shù)僅是1與，因此必得。

現(xiàn)在從等式兩邊消去得等式

簡(jiǎn)要重述相同的論證，可以消去(等于)得到新的等式

繼續(xù)這個(gè)過(guò)程直到所有的或所有的被消去。但是如果所有的被消去，則等式的左邊等于1，所以右邊沒(méi)有任何。類似地，如果都被消去則必然被消去。 的個(gè)數(shù)一定等于的個(gè)數(shù)。

我們已證明:如果

其中所有與都是素?cái)?shù)，則r=s。重排使得

這就完成了僅有一種表示方法將n表示成素?cái)?shù)乘積的證明。

算術(shù)基本定理說(shuō)明每個(gè)整數(shù)可表示成素?cái)?shù)乘積。接下來(lái)的問(wèn)題就是，如何把一個(gè)整數(shù)表示成素?cái)?shù)乘積。

如果n相當(dāng)小(例如n=180)，可用檢查法分解n，

如果n比較大(例如n=9105293)，求因數(shù)分解會(huì)更困難。一種方法是用素?cái)?shù)2,3,5,7, 11,…試除n直到得到一個(gè)因數(shù)為止。對(duì)于n=9105293，經(jīng)過(guò)試除后，得到了完全素因數(shù)分解

如果n本身不是素?cái)?shù)，則必有整除n的素?cái)?shù)。要知道為什么成立，可以觀察如果p是整除n的最小素?cái)?shù)，則n=pm, ，從而，兩邊取平方根得。這就給出了將任何整數(shù)n表示成素?cái)?shù)乘積的下述十分簡(jiǎn)單明了的方法：

要將n表示成素?cái)?shù)乘積，用小于等于的海個(gè)數(shù)(或正好每個(gè)素?cái)?shù))2,3,...試除它，如果沒(méi)有求得整除n的整數(shù)，則n本身是素?cái)?shù)，否則求得的第一個(gè)因數(shù)是素?cái)?shù)p，分解得n=pm，然后對(duì)m重復(fù)這個(gè)過(guò)程。

雖然這是一個(gè)效率非常低的過(guò)程，但對(duì)適當(dāng)大的數(shù)，比如說(shuō)不超過(guò)10位的數(shù)，在計(jì)算機(jī)上可以工作得很好。對(duì)于像這樣的數(shù)，將非常耗時(shí)，以至于計(jì)算機(jī)無(wú)法在可接受時(shí)間內(nèi)解決問(wèn)題。

這就產(chǎn)生了下述兩個(gè)緊密相關(guān)的問(wèn)題:

問(wèn)題1 如何分辨已知數(shù)n是素?cái)?shù)還是合數(shù)?

問(wèn)題2 如果n是合數(shù)，如何將它分解成素?cái)?shù)的乘積?

雖然看起來(lái)似乎這兩個(gè)問(wèn)題相同，事實(shí)表明問(wèn)題1要比問(wèn)題2容易回答，這些問(wèn)題將在另外的文章中予以討論。

總結(jié)，

1. 素?cái)?shù)合數(shù)是對(duì)自然數(shù)的一種分類，用的是整除性，這樣，大數(shù)可以用小數(shù)表示，且合數(shù)可以歸結(jié)到素?cái)?shù)問(wèn)題
2. 算術(shù)基本定理的證明，把問(wèn)題分裂成兩個(gè)子問(wèn)題分別解決，并使用了歸納法。