初等數(shù)論1 - 整除理論

1、整 除 理 論11、素數(shù) (1)、素因子 (2)、素數(shù)分布 (3)、素數(shù)搜尋 (4)、素性判定2、GCD和LCM2定義 若整數(shù)a 0，1，并且只有約數(shù) 1和 a，則稱a是素數(shù)（或質數(shù)）； 否則稱a為合數(shù)。定理 任何大于1的整數(shù)a都至少有一個素約數(shù)。推論 任何大于1的合數(shù)a必有一個不超過a1/2的素約數(shù)。 定理 (算術基本定理) 任何大于1的整數(shù)n可以唯一地表示成(標準分解式) 其中p1 , p2, , pk 是素數(shù)，p1 p2 1)是素數(shù)，則a = 2，并且n是素數(shù)。(3+k)ab-1 必非素數(shù)。4)、形如2(2n)+1 (n = 0, 1, 2, )的數(shù)稱為Fermat數(shù)。 Fermat曾猜

2、測是素數(shù)：F0,F1,F2,F3,F4是素數(shù)，F(xiàn)5=641*6700417是合數(shù)。 5)、形如4n 3的素數(shù)有無限多個。 6)、越往后越稀疏：在正整數(shù)序列中, 有任意長的區(qū)間中不含有素數(shù)。 對于大于等于2的整數(shù)n，連續(xù)n-1個整數(shù)n!2, n!3, , n!n都不是素數(shù)。 5素數(shù)分布7)、素數(shù)大小粗糙的估計 pn p1p2pn-1 1，n 1。 pn 22n。 (n) (log2n)/2。8)、素數(shù)定理：6素數(shù)搜尋尋找素數(shù)的方法：Eratosthenes篩法。7素性判定確定型算法試除法 嘗試從2到N的整數(shù)是否整除N。 威廉斯方法、艾德利曼、魯梅利法、馬寧德拉.阿格拉瓦法(log(n)的多項式級

3、算法)隨機算法費馬測試 利用費馬小定理來測試。 若存在a，(a, n) = 1，使得a n 1 1 mod n成立，則稱n是關于基數(shù)a的偽素數(shù)（ Fermat偽素數(shù)，Carmichael 數(shù) ）。 米勒-拉賓法、8GCD和LCM定義 整數(shù)a1, a2, , ak的公共約數(shù)稱為a1, a2, , ak 的公約數(shù)。 不全為零的整數(shù)a1, a2, , ak 的公約數(shù)中最大一個叫做a1, a2, , ak 的最大公約數(shù)（或最大公因數(shù)），記為(a1, a2, , ak)。 由于每個非零整數(shù)的約數(shù)的個數(shù)是有限的，所以最大公約數(shù)是存在的，并且是正整數(shù)。 如果(a1, a2, , ak) = 1，則稱a1,

4、a2, , ak 是互素的。 如果(ai, aj) = 1，1 i, j k，i j，則稱a1, a2, , ak 是兩兩互素的。 a1, a2, , ak 兩兩互素可以推出(a1, a2, , ak) = 1，反之則不然。定義 整數(shù)a1, a2, , ak 的公共倍數(shù)稱為a1, a2, , ak 的公倍數(shù)。 整數(shù)a1, a2, , ak 的正公倍數(shù)中最小的一個叫做a1, a2, , ak 的最小公倍數(shù)，記為a1, a2, , ak。9GCD和LCMn的標準分解式：n的正因數(shù)： n的正倍數(shù) ：10帶余數(shù)除法 設a與b是兩個整數(shù)，b 0，則存在唯一的兩個整數(shù)q和r，使得 a = bq r，0 r

5、 |b|。定理 若a = bq r，則(a, b) = (b, r)。實際上給出一個求最大公因子的方法。推論 設a1, a2, , an為不全為零的整數(shù)，以y0表示集合 A = y：y = a1x1 anxn，xiZ，1 i n 中的最小正數(shù)，則 對于任何yA， y0y； 特別地， y0ai，1 i n。證明： 設y0 = a1x1 anxn， 對任意的y = a1x1 anxnA，存在q, r0Z，使得 y = qy0 r0，0 r0 y0 。 因此 r0 = y qy0 = a1(x1 qx1) an(xn qxn)A。 如果r0 0，那么，因為0 r0 y0，所以r0是A中比y0還小的正

6、數(shù)， 這與y0的定義矛盾。所以r0 = 0，即y0y。 顯然aiA（1 i n），所以y0整除每個ai（1 i n）。GCD和LCM11定理 設a1, a2, , ak Z，記 A = y：y = ，xiZ， i k 。如果y0是集合A中最小的正數(shù)，則y0 = (a1, a2, , ak)。 推論 設d是a1, a2, , ak的一個公約數(shù)，則d(a1, a2, , ak)。 最大公約數(shù)不但是公約數(shù)中的最大的，而且是所有公約數(shù)的倍數(shù)。定理 記d = (a1, a2, , ak)，則 (a1/d, a2/d, , ak/d)=1。 特別地, (a/(a,b), b/(a,b)=1 。 定理 (a

7、1, a2, , ak) = 1的充要條件是存在整數(shù)x1, x2, , xk，使得 a1x1 a2x2 akxk = 1。定理 對于任意的整數(shù)a，b，c，下面的結論成立： () 由bac及(a, b) = 1可以推出bc； () 由bc，ac及(a, b) = 1可以推出abc。推論 若p是素數(shù)，則下述結論成立： () pab pa或pb； () pa2 pa。GCD和LCM12推論 若 (a, b) = 1，則(a, bc) = (a, c)。 （備注1）推論 若 (a, bi) = 1，1 i n，則(a, b1b2bn) = 1。定理 對于任意的n個整數(shù)a1, a2, , an ，記 （

8、備注2） (a1, a2) = d2， (d2, a3) = d3， ， (dn-2, an-1) = dn-1， (dn-1, an) = dn， 則 dn = (a1, a2, , an)。GCD和LCM13定理 下面的等式成立：() a, 1 = |a|，a, a = |a|；() a, b = b, a；() a1, a2, , ak = |a1|, |a2| , |ak|；() 若ab，則a, b = |b|。推論 由a,b=ab/(a,b)有：兩個整數(shù)的任何公倍數(shù)可以被它們的最小公倍數(shù)整除。 定理 對于任意的n個整數(shù)a1, a2, , an ，記 a1, a2 = m2， m2,

9、a3 = m3， ， mn2, an1 = mn1， mn1, an = mn，則 a1, a2, , an = mn。推論 若m是a1, a2, , an的公倍數(shù)，則a1, a2, , an | m。GCD和LCM14定理 整數(shù)a1, a2, , an 兩兩互素，即(ai, aj) = 1，1 i, j n，i j的充要條件是 a1, a2, , an = a1 a2 an 。 如果m1, m2, , mk是兩兩互素的整數(shù)，那么 要證明m = m1m2mk整除某個整數(shù)Q， 只需證明對于每個i，1 i k，都有miQ。這一點在實際計算中是很有用的。對于多項式f(x)，要驗證命題“mf(n)，n

10、Z”是否成立，可以驗證“mf(r)，r = 0, 1, , m 1”是否成立。這需要做m次除法。但是，若分別驗證“mif(ri)，ri = 0, 1, , mi 1，1 i k”是否成立，則總共需要做m1 m2 mk次除法，顯然遠遠少于m1m2mk = m。 GCD和LCM15輾轉相除法/Euclid算法 設a與b是兩個整數(shù)，b 0，依次做帶余數(shù)除法： a = bq1 r1， 0 r1 |b|， b = r1q2 r2， 0 r2 r1 ， rk 1 = rkqk + 1 rk + 1， 0 rk + 1 rk ， (1) rn 2 = rn 1qn rn， 0 rn r1 r2 ，所以式(1

11、)中只包含有限個等式。 GCD和LCM16輾轉相除法/Euclid算法 引理 用下面的方式定義Fibonacci數(shù)列Fn： F1 = F2 = 1，F(xiàn)n = Fn 1 Fn 2，n 3，那么對于任意的整數(shù)n 3，有 Fn n 2， (2)其中 =(1+51/2)/2。定理(Lame) 設a, bN，a b，使用在式(1)中的記號，則 n 5log10b。 定理 使用式(1)中的記號，記P0 = 1，P1 = q1，Pk = qkPk 1 Pk 2，k 2，Q0 = 0，Q1 = 1，Qk = qkQk 1 Qk 2，k 2，則aQk bPk = (1)k 1rk，k = 1, 2, , n 。 (3)利用輾轉相除法可以求出整數(shù)x，y，使得ax by = (a, b) 。 (4)為此所需要的除法次數(shù)是O(log10b)。GCD和LCM17輾轉相除法/Euclid算法 但是，如果只需要計算(a, b)而不需要求出使式(4)成立的整數(shù)x與y，則所需要的除法次數(shù)還可更少一些。設a和b是正整數(shù)，基于下面的四個基本事實，只使用被2除的除法運算和減法運算就可以計算出(a, b)。() 若ab，則(a, b) = a；() 若a = 2a1，2 | a1 ， b