初等數(shù)論中的幾個重要定理

1、第五節(jié)初等數(shù)論中的幾個重要定理根底知識定義(歐拉(Euler)函數(shù))一組數(shù) x1,x2, ,xs稱為是模 m的既約剩余系,如果對任意的1 j s, (Xj,m) 1且對于任意的a Z ,假設(shè)(a, m)= 1,那么有且僅有一個Xj是a對*H m 的剩余,即a Xj(modm).并定義(m) s 1,2, ,m中和m互質(zhì)的數(shù)的個數(shù), (m) 稱為歐拉(Euler)函數(shù).這是數(shù)論中的非常重要的一個函數(shù),顯然(1) 1 ,而對于m 1, (m)就是1,2,m 1中與m互素的數(shù)的個數(shù),比方說p是素數(shù),那么有 (p) p 1.,一 1、引理：(m) m(1);可用容斥定理來證(證實略).P|mPP為質(zhì)數(shù)

2、定理 1：(歐拉(Euler)定理)設(shè)(a,m)=1,那么 a (m) 1(mod m).證實：取模m的一個既約剩余系 “也,bs,(s(m),考慮ab1 ,ab2, ,abs,由于a與m互質(zhì),故abj (1 j s)仍與m互質(zhì),且有 abiabj( 1 i j s),于是對每個1 js都能找到唯一的一個1(j) s ,使彳a abjb(mod m),這種對應(yīng)關(guān)系 是sssss的,從而(abj)b (j)(modm)bj (modm),as( bj) ( bj)(mocm)oj 1j 1j 1j 1j 1s(m,bj) 1,as 1(mod m),故 a (m) 1(modm).證畢.j 1分

3、析與解答：要證 a (m) 1(mod m),我們得設(shè)法找出(m)個n相乘,由(m)個數(shù)我們想到1,2, m中與m互質(zhì)的(m)的個數(shù)：a1,a2,a (m),由于(a, m) = 1 ,從而aa1,aa2, ,aa也是與 m互質(zhì)的 (m)個數(shù),且兩兩余數(shù)不一樣,故 a a2 a aa1,aa2, , aa (m)a (m) a a? a (modm ),而(a a2a m)= 1,故 a (m) 1(mod m).這是數(shù)論證實題中常用的一種方法,使用一組剩余系,然后乘一個數(shù)組組成另外一組剩余系來解決問題.a(mod p).定理2：(費爾馬(Fermat)小定理)對于質(zhì)數(shù)p及任意整數(shù)a有ap設(shè)p

4、為質(zhì)數(shù),假設(shè)a是p的倍數(shù),那么ap 0 a(mod p).假設(shè)a不是p的倍數(shù),那么(a,p) 1 由引理及歐拉定理得(p) p 1,a (p) 1(modp),ap1 1(modp),ap a(modp),由此即得.一一*p 1定理2推論：設(shè)p為質(zhì)數(shù),a是與p互質(zhì)的任一整數(shù),那么ap1(modp).定理3：(威爾遜(Wilson )定理)設(shè)p為質(zhì)數(shù),那么(p 1)! 1(mod p).分析與解答：受歐拉定理的影響,我們也找 p 1個數(shù),然后來對應(yīng)乘法.證實：對于(x,p) 1 ,在x,2x, ,(p 1)x中,必然有一個數(shù)除以p余1,這是由于x,2x, , (p 1)x那么好是p的一個剩余系去

5、 0.從而對x 1,2,p1, y1,2, p 1,使得 xy 1(mod p);假設(shè) xyxy2(m0dp) ,(x, p)1 ,那么 x(y y?) 0(mod p), p|(yy?),故對于0,丫2 1,2, , p 1,有xy xy2 (mod p).即對于不同的x對應(yīng)于不同的 y ,即 1,2, , p 1中數(shù)可兩兩配對,其積除以 p余1,然后有x ,使x2 1(mod p),即與它自 己配對,這時 x2 1 0(mod p) , (x 1)(x 1) 0(mod p) , x 1或 x 1(mod p), x p 1 或 x 1.除x 1, p 1外,別的數(shù)可兩兩配對,積除以p余1

6、.故(p 1)! (p 1) 1 1(modp). 定義：設(shè) 匕(x)為整系數(shù)多項式(1 j k ),我們把含有x的一組同余式 fj (x) 0(modmj)(1 j k)稱為同余方組程.特別地,當fi(x)均為x的一次整系數(shù) 多項式時,該同余方程組稱為一次同余方程組.假設(shè)整數(shù)c同時滿足：fj (c) 0(mod mj)1 j k,那么剩余類 M c x|x Z,x c(mod m)(其中 m m,m2, ,mJ)稱為同 余方程組的一個解,寫作x c(mod m)定理4：(中國剩余定理)設(shè)m1,m2, , mk是兩兩互素的正整數(shù),那么對于任意整數(shù)a1,a2,ak, 一次同余方程組 x aj (

7、mod mj) , 1 j k必有解,且解可以寫為:xM1N1alM2N2a2M kNkak(mod m)mi這里 m m1m2 mk, M , 一(1 i k),以及 N j 滿足 M j N j 1(modmj), 1 j k(即Nj為Mj對卞Hmj的逆).中國定理的作用在于它能斷言所說的同余式組當模兩兩互素時一定有解,而對于解的形式并不重要.定理5：(拉格郎日定理) 設(shè)p是質(zhì)數(shù),n是非負整數(shù),多項式 f (x) anxna1x a0是一個模p為n次的整系數(shù)多項式(即 咻an),那么同余方程f (x) 0(modp)至多有n個 解(在模p有意義的情況下).定理6：假設(shè)l為a對卞m的階,s為

8、某一正整數(shù),滿足 as 1(mod m),那么s必為l的倍數(shù).以上介紹的只是一些系統(tǒng)的知識、 方法,經(jīng)常在解決數(shù)論問題中起著突破難點的作用. 另外 還有一些小的技巧那么是在解決、 思考問題中起著排除情況、輔助分析等作用,有時也會起到意想不到的作用,如:1(mod 8) n為奇數(shù)時0(mod 4) n為偶數(shù)時0(mod9)3整除n時.這里我們0(mod 3) 3不整除n時只介紹幾個較為直接的應(yīng)用這些定理的例子.典例分析例 1.設(shè)(91,ab) 1,求證：91|(a12 b12).證實：由于 91 7 13,故由(91,ab) 1 知(91,a) 1 ,從而(7,a) 1,(13,a) 1 ,但是

9、(7) 6, (13) 12 ,故由歐拉定理得：a12 (a6)2 12 1(mod 7), a12 1(mod13),從而 a12 1(mod91)；同理,b12 1(mod91).于是,a12 b12 1 1 0(mod 91),即 91|(a12 b12).注明：現(xiàn)考慮整數(shù)a的哥an所成的數(shù)列：a,a2, ,an,假設(shè)有正整數(shù)k使ak 1(mod m),那么有 an ar (mod m),其中 n kq r,0 r k；因而關(guān)于mod(m),數(shù)列a,a2, ,an,的項依次同余于a,a2, ,ak, a,a2, ,ak, a,這 個數(shù)列相繼的k項成一段,各段是完全相同的,因而是周期數(shù)列.

10、如下例： 例2.試求不大于100,且使11|(3n 7n 4)成立的自然數(shù)n的和.解：通過逐次計算,可求出 3n關(guān)于mod11的最小非負剩余(即為被11除所得的余數(shù))為：3 3(mod11),32 9(mod11),33 5(mod11), 34 5 3 4(mod11),35 4 3 1(mod11)因而通項為3n的數(shù)列的項的最小非負剩余構(gòu)成周期為5的周期數(shù)列:3, 9, 5, 4, 1, 3, 9, 5, 4, 1,類似地,經(jīng)過計算可得 7n的數(shù)列的項的最小非負剩余構(gòu)成周期為10的周期數(shù)列:7, 5, 2, 3, 10, 4, 6, 9, 8, 1 ,于是由上兩式可知通項為 3n 7n 4

11、的數(shù)列的項的最小非負剩余,構(gòu)成周期為10 (即上兩式周期的最小公倍數(shù))的周期數(shù)列：3, 7, 0, 0, 4, 0, 8, 7, 5, 6,這就說明,當 1 n 10時,當且僅當 n 3,4,6時,3n 7n 4 0(mod11),即 11|(3n 7n 4)；又由于數(shù)列的周期性,故當 10k 1n 10(k 1)時,滿足要求的n只有三個,即10k 3,10k4,10k 6從而當1 n 100寸,滿足要求的n的和為:99(10k 3) (10k 4) (10k 6)30k 13k 0k 0930 k 10k 013 30 45 130 1480.下面我們著重對Fetmat小定理及其應(yīng)用來舉例：

12、例3.求證：對于任意整數(shù) x, 1x5 1x3 x5315是一個整數(shù).15 13 75證實：令f (x) -x -xx,那么只需證15f (x) 3x53155x37x是15的倍數(shù)即可.由 3, 5 是素數(shù)及 Fetmat 小定理得 x5 x(mod 5) , x3 x(mod 3),53533x 5x 7x 3x 7x 0(mod 5) ； 3x 5x 7x 2x x 0(mod 3)而(3, 5) =1,故 3x5 5x3 7x 0(mod15),即 15 f (x)是 15 的倍數(shù).所以 f(x)是整數(shù).13例4 .求證：2730 |n n ( n為任意整數(shù)).證實：令 f(n) n13

13、 n,那么 f(n) n(n 1)(n 1)(n2 n 1)(n2 n 1)(n6 1)；所以 f (n)含有因式 n7 n, n5 n,n3 n, n2 n由 Fetmat 小定理,知 13| n13 n, 7| n7 n,5 |n5 n,31 n3 n,2| n2 n又13, 7, 5, 3, 2兩兩互素,所以 2730=13 75 3 2能整除n13例5.設(shè)a, b,c是直角三角形的三邊長.如果a,b,c是整數(shù),求證：abc可以被30整除.證實：不妨設(shè)c是直角三角形的斜邊長,那么C2 a2 b2.假設(shè) 2卡 a,咻b, 2 卡 c,貝 U c2 a2 b2 1 1 0(mod 2),又由

14、于 c2 1(mod2)矛盾！ 所以2| abc.假設(shè) 3 *a , 3 +b ,斗 c,由于(3k 1)2 1(mod 3),那么 a2 b2 1 1 2(mod3),又2c 1(mod 3),矛盾！從而 3| abc.假設(shè) 5 *a, 5 *b, 5 *c,由于(5k 1)2 1(mod 5) , (5k 2)2 1(mod 5),所以 a2 b22或 0(mod5)與 c21(mod 5)矛盾！從而5| abc.又(2,3,5)=1 ,所以 30| abc.下面講述中國剩余定理的應(yīng)用例6.證實：對于任意給定的正整數(shù)n ,均有連續(xù)n個正整數(shù),其中每一個都有大于1的平方因子.證實：由于素數(shù)有

15、無窮多個,故我們可以取n個互不相同的素數(shù) p1,p2, ,pn,而考慮同余組 x i(mod p2),i 1,2, ,n 222由于p1 , p2 , pn顯然是兩兩互素的,故由中國剩余定理知,上述同余組有正整數(shù)解.于是,連續(xù)n個數(shù)x 1,x 2, ,x n分別被平方數(shù)p；, p22, , pn2整除.注：(1)此題的解法表達了中國剩余定理的一個根本成效,它常常能將“找連續(xù)n個正整數(shù)具有某種性質(zhì)的問題轉(zhuǎn)化為“找n個兩兩互素的數(shù)具有某種性質(zhì),而后者往往是比擬容易解決的.(2)此題假設(shè)不直接使用素數(shù),也中以采用下面的變異方法：由費爾馬數(shù)Fk 22k 1(k 0)兩兩互素,故將中的p：轉(zhuǎn)化為F,(i

16、 1,2, ,n)后,相應(yīng)的同余式也有解,同樣可以導(dǎo)出證實.例7.證實：對于任意給定的正整數(shù)n ,均有連續(xù)n個正整數(shù),其中每一個都不是哥數(shù).分析：我們來證實,存在連續(xù) n個正整數(shù),其中每一個數(shù)都至少有一個素因子,在這個數(shù)的 標準分解中僅出現(xiàn)一次,從而這個數(shù)不是哥數(shù).證實：取n個互不相同的素數(shù) p1,p2, , pn,考慮同余組x i(mod p2),i 1,2, , n222 -由于p1 , p2 , pn顯然是兩兩互素的,故由中國剩余定理知,上述同余組有正整數(shù)解.對于1 i n由于x i p/mod p2),故p：|(x i),但由式可知pN(x i),即pi在(x i)的標準分解中恰好出現(xiàn)

17、一次,故 x 1, x 2, ,x n都不是哥數(shù).例8.設(shè)n,k是給定的偶數(shù),n 0且k(n 1)是偶數(shù).證實：存在整數(shù) x,y使得(x,n) (y, n) 1,且x y k(modn).證實：我們先證實,當 n為素數(shù)哥p時結(jié)論成立.實際上,能夠證實,存在 x,y使假設(shè)p 2,那么條件說明k為偶數(shù),此時可取假設(shè) p 2,貝Ux 1, y k 1與 x 2, y k 一般情形下,設(shè) npjp；2p：r,i 1,2,個pi存在整數(shù)xi, yi使得pi yi且xi yi 同余式 x xi(mod pi i )(i 1,2, r)同余式 y yi(mod pi i)(i 1,2, ,r) 現(xiàn)不難驗證解x,y符合問題中的要求：因于是(xy, n) 1 ,又由知 x y xix 1, y k 1 ；2中有一對滿足要求.,r是n的一個標準分解,上面已經(jīng)證實,對每k (i 1,2, r),而由中國剩余定理,有解x ,有解y.pWy,故 p*xy(i 1,2, r),yi(modpj)(i 1,2, ,r),故 x y k(mod n).將一個關(guān)于任意正整數(shù) n的問題,化