001　算術基本定理
　　每個大於1的正整數均可唯一地表為質數的乘積。
　　大數學家高斯曾說：「數學是科學的王后，而數論則是數學的王后。」這句話雖然流露出高斯對數論的過分偏愛，但也表明數論在數學家心目中的崇高地位。從古希臘的歐幾里得開始，幾千年來許多數學家都對數論產生過濃厚的興趣，並進行了大量深入的研究。時至今日，儘管數學已經發展成為一門內容龐大、應用廣泛的學科，但還有很多在敘述上簡明易懂的關於正整數的問題未得到完全的解決，這真令人感到不可思議。特別是其中的一些數論問題（如哥德巴赫猜想）幾乎是家喻戶曉，幾百年來它們像謎一樣吸引著數學家以及無數的數學愛好者。
　　在正整數或正整數的理論中，有一類稱為質數的數扮演著非常重要的角色。質數在正整數理論中的地位類似於元素在化學中或基本粒子在物理學中的地位。我們知道，質數是指那些大於1且除了1和它自身外再沒有其他因數的正整數。前10個質數為
2，3，5，7，11，13，17，19，23，29
　　如果一個正整數具有除了自身和1以外的其他因數，則稱為合數。這樣，可以把所有的正整數分成三類：1，質數，合數。
　　質數的重要性首先表現在數的乘法分解方面。因為每個大於1的正整數a，如果本身不是質數，則存在不等於a和1的因數b，此時可令a=bc，其中b，c都大於1。如果b（或c）不是質數，則重複這種分解過程，又可分解出b=b1b2（或c=c1c2），顯然a>b>b1>1（或a>c>c1>1）。這個分解過程不能無限地重複下去，換句話說，有限步後就可以把a分解成一些質數的乘積。我們得到的結論是：每個大於1的正整數均可表示為若干質數的乘積。從這個意義上講，質數是構成正整數的基本元素。因此，在正整數理論中遇到的許多命題大多能歸結為有關質數的研究，也就不足為奇了。
　　算術基本定理的內容由兩部分構成：①分解的存在性，指的是每個大於1的正整數均可分解成一些質數的乘積；②分解的唯一性，即如果不考慮諸質數的排列順序，則把正整數分解成質數乘積的方式還是唯一的。例如，21的質數分解只有21=3×7和21=7×3，但本質上屬於同一種分解。算術基本定理是整數理論中最為基本的一個命題，也是許多其他命題的邏輯支撐點和出發點。上面已經證明了分解的存在性部分，其唯一性部分看起來似乎是顯而易見的，但要嚴格地證明它卻絕非易事。雖然它的證明較為初等，卻需要精細的推理過程，這充分反映了數學學科所特有的思維風格。
　　先介紹西元前300年的歐幾里得在其巨著《幾何原本》中所給的證明。下面只考慮正整數。如果d既是a的一個因數，又是b的一個因數，則稱d為a和b的一個公因數。在a和b的所有公因數中的最大者稱為最大公因數，記為（a，b）。歐幾里得發明了一種「輾轉相除法」，用來求兩個正整數的最大公因數，從此導出了一個十分重要的結論：如果d是a和b的最大公因數，則存在整數x和y滿足d=ax+by。這個結論從現代數學的觀點也是非常基本的，如果讀者熟悉近世代數，它相當於說全體整數構成的集合不僅是一個環，而且是一個主理想整環。這裡當然不會使用這個近代的結論，而是要從歐幾里得發現的這個最大公因數的表示公式出發去證明質數的一個基本性質：設p為質數，如果p整除兩個正整數a和b的乘積，則p必整除其一，即p整除a或者p整除b。
　　顯然，如果p不整除a，則p和a的最大公因數不是p，但p為質數，表明p和a的最大公因數只能為1。根據上述歐幾里得導出的結論，存在整數x和y使得1=px+ay。兩邊用b去乘，有b=bpx+bay。因為等式右邊的兩項分別能被p整除，從而等式左邊的b也能被p整除。由此即證所述結論。