整除

　　數論中一個最基本的概念。任給二整數α與b，其中b≠0，如果有一個整數с使α=bс，就稱b能整除α，記作b│α。此時把b叫作α的因數，α叫叫作b的倍數。如果b不能整除α，就記作b

α。通常，因數總假定是正的。從整除的定義出發，以下一些性質是明顯的：①若 b│ α，с│ b，則с│ α；②若 b│ α，則с b│с α，反之亦然；③若с│ α，с│ b，則對任意的整 m， n，有с│ m α+ n b；④若 b｜ α，則 。一般地，有所謂的帶餘除法，即設 α、 b是二整數，其中 b＞0，則存在兩個惟一的整數 q和 r，使得 α= b q+ r，0≤ r＜ b， r叫作 α被 b除所得到的餘數，記為＜ α＞ _b= r顯然， b)整除 α當且僅當 r=0。

　　最大公因數與輾轉相除法　設α₁，α₂，…，α_n(n≥2)是n個整數，若整數d＞0是它們之中每一個的因數，那麼d就叫作α₁，α₂，…，α_n的一個公因數，諸公因數中最大的一個叫作最大公因數，記作(α₁，α₂，…，α_n)。如果(α₁，α₂)=1，那麼α₁和α₂叫做互素或互質。設α、b是任意兩個正整數，由帶餘除法可得下列諸式：

因為 b＞ r ₁＞ r ₂＞…，故經有限步之後， r _n+1=0，且( α， b)= r _n。這就叫做輾轉相除法，又稱歐幾裡得算法，它是古希臘數學傢 歐幾裡得於公元前4世紀給出的。他還證明瞭存在二整數 l和 m使得( α， b))= l α+ m b)。顯然， α、 b)的任何公因數是( α， b)的因數。

　　最小公倍數　設α₁，α₂，…，α_n(n≥2)是n個正整數，如果m是這n個數中每一個數的倍數，那麼m就叫做這n個數的一個公倍數，一切公倍數中最小的正整數叫做最小公倍數，記為[α₁，α₂，…，α_n]。因為乘積α₁α₂…α_n就是α₁，α₂，…，α_n的一個公倍數，所以最小公倍數總是存在的。設α、b是任意二正整數，則：①α、b的所有公倍數就是[α，b)]的所有倍數；②[α，b](α，b)=αb。

　　素數和算術基本定理　正整數可以分成三類；①1，隻有正整數1是它的因數；②素數p，p＞1，隻有正整數1和p是它的因數；③復合數m，有大於1同時小於m的因數。歐幾裡得證明瞭素數的個數是無限的。因為，如果素數有限，設為p₁，p₂，…，p_k而整數p₁，p₂，…p_k+1中必有不同於p₁，p₂，…，p_k的素因數。他還證明瞭若素數p│αb，則p│α或p│b。由此可得算術基本定理：任一大於1的整數數n，如果不計順序，那麼隻有惟一的方法表示成素數的乘積。由這個定理可知，任一大於1的整數n可惟一地分解成標準形式

，其中 p ₁＜ p ₂<…＜ p _k是素數。作為算術基本定理一個簡單而直接的應用，設

，則 ，其中 。多於兩個正整數的最大公因數和最小公倍數可以仿此求出。算術基本定理又叫整數的惟一分解定理，是數論中一個基本的定理，許多結果依賴於它的成立。 代數數論研究的主要問題之一，就是研究在給定的代數數域中代數整數的惟一分解定理是否成立。

　　如何把一個給定的大的正整數分解為它的標準形式，一直是人們所關心和研究的問題，它不僅具有理論意義，而且有實際應用。雖然已經得到一些較有效的算法來判斷一個大數是否素數，但是分解一個大數，仍然十分困難，即使借助於電子計算機也要花費驚人的時間。利用大數分解的困難性，1977年，R.L.裡弗斯特等人設計出一種能夠公開密鑰的密碼。

　　埃拉托斯特尼篩法　大約在公元前250年，古希臘數學傢埃拉托斯特尼提出一個造出不超過N的素數表的方法，它基於這樣一個簡單的性質：如果n≤N，而n是復合數，則n必為一不大於

的素數所整除。具體作法如下：先列出不超過 的全體整數，設為 ，然後依次排列2，3，…， N，在其中留下 p ₁=2，而把 p ₁的倍數全劃掉，再留下 p ₂，而把 p ₂的倍數全劃掉，繼續如此往下做，直到最後留下 p _r而劃去 p _r的倍數。所留下的整數就是不超過 N的全體素數。這就是著名的埃拉托斯特尼篩法。近代素數表都是由此法略加變化造出。1914年，D.H.萊默爾發表瞭1到10006721的素數表。1951年，J.P.庫利克等又增加瞭從10006721到10999997間的素數。最大的素數表是D.B.紮蓋爾1977年發表的，列出瞭不超過5× 10 ⁷的素數。埃拉托斯特尼篩法的改進和發展，是近代解析數論的重要工具之一。