初等數(shù)論第三章同余

1、第三章 同 余 1 同余的概念及其基本性質(zhì) 定義1設(shè)m Z，稱(chēng)之為模。若用m去除兩個(gè)整數(shù)a與b所得的余數(shù)相同, 則稱(chēng)a, b對(duì)模m同余，記作：a b (mod m)；若所得的余數(shù)不同，則稱(chēng)a, b對(duì)模m 不同余，記作： a b(mod m)。 例如， 8 1(mod 7)，；所有偶數(shù) a 0(mod 2)，所有奇數(shù) a 1(mod 2)。 同余是整數(shù)之間的一種 關(guān)系，它具有下列性質(zhì) ： 1、a a(mod m)； (反身性) 2、若 a b (mod m)，則 b a (mod m);(對(duì)稱(chēng)性) 3、若 a b (mod m)，b c (mod m)，則 a c(mod m);(傳遞性) 故同

2、余關(guān)系是等價(jià)關(guān)系 。 定理1 整數(shù)a,b對(duì)模m同余的充分必要條件是m|(a b)，即卩a b mt， t Z。 證明 設(shè) a mq1 r1， b mq2r2， 0 r1,r2m， 則a b(mod m) r1 r2 a bm(q1 q2)m|(ab)。 性質(zhì)1 (1)若 ai bi (mod m)， a?b2 (mod m)，貝U aia?bib2(mod m)； (2) 若 a b c (mod m),貝U a c b (mod m)。 性質(zhì)2若a1b1 (modm)，a2b2 (modm),貝U a1a2b1b2(mod m); 特別地，若 a b (mod m)，貝U ka kb (mo

3、d m)。 定理2 若A 1k B 1 k (mod m)， xi yi (mod m)， i 1,2, ,k， 則A 1 k x1 1 1k k xk k B 1k y1 1 1k k ykk (mod m)；特別地，若 ai bi (mod m)， i 0,1,2, ,n，則 n anx n1 an 1x a0 nn 1 bnxbn 1x b0 (mod m)。 性質(zhì)3 若a a1d， b b1d， (d,m) 1， a b(mod m)， 則 a1 b1 (mod m)。 性質(zhì)4(1)若a b (mod m), k 0,貝U ak bk(modmk); 若a b (mod m), d是a

4、, b及m的任一公因數(shù)，則 (mod m) d d d 性質(zhì)5 右a b (mod mi), i 1,2, k,則a b (mod m!, m2, mk ) 反之亦然。 性質(zhì)6 右a b (mod m), d | m, d 0,則a b (mod d) 性質(zhì)7 右a b(mod m),貝U (a, m) (b, m), 因而右d能整除a,b及m兩數(shù) 之一，則d必能整除a,b中的另一數(shù)。 例1求3406寫(xiě)成十進(jìn)位數(shù)時(shí)的個(gè)位 數(shù)碼。 解 事實(shí)上，只需求滿(mǎn)足 3406 a (mod 10)， 0 a 9的數(shù)a 因?yàn)?32 91 (mod 10)，所以 3 406 ( 32 ) 203 ( 1)203

5、1 9 (mod 10), 即個(gè)位數(shù)碼是9 例2證明：當(dāng)n為奇數(shù)時(shí)，3| 2n 1,當(dāng)n為偶數(shù)時(shí)，3 | 2n 1。 證明 因?yàn)?21 (mod 3),所以 2n 1( 1)n 1 (mod 3), 當(dāng) n為奇數(shù)時(shí)，2n1( 1)n1110 (mod 3),故 3|2n1, 當(dāng) n為偶數(shù)時(shí)，2n1( 1)n1112 (mod 3),故 3 12n1。 同余性質(zhì)在算術(shù)中的一些應(yīng)用。 一、檢查因數(shù)的方法 1、一整數(shù)能被3 (或9)整除的充分必要條件是它的十進(jìn)位數(shù)碼之和能被 3 (或9)整除。 證明 只需討論正整數(shù)即可。任取 a Z ，則 a 可以寫(xiě)成十進(jìn)位的形式： a an10n an 110n

6、1 a0， 0 ai 10，于是，由 10 1 (mod 3) 可知 a an an 1 a0 (mod 3)，從而 3 |a 3 |an an 1 a0。 對(duì)于 9 同理可證。 2、設(shè)正整數(shù) a a n 1000 n an 11000 n 1 a0， 0 ai 1000 ，則 7(或 11或13) |a的充分必要條件是 7 (或11或13) | (ao a?) (ai as )。 證明 因?yàn)?7X 11 x 13=1001。 例 3 a=5874192 能被 3 和 9 整除。 例 4 a=435693 能被 3 整除，但不能被 9 整除。 例5 a=637693能被7整除；a=能被13整除

7、。 二、棄九法 (驗(yàn)算整數(shù)計(jì)算結(jié)果的方法) 例6 設(shè)a=28997，b=39495, P=ab=15，檢查計(jì)算是否正確。 解 令 a an10n n1 an 110 a0， 0 ai 10 b bm10m m1 bm 110m 1 b0， 0 bj 10 P cl10l cl 110l 1 c 0， 0 c k 10 nml 則 ( ai)( bj)ck (mod 9)(*) i 0 j 0 k 0 若(*)不成立，則Pmab,故在本題中，計(jì)算不正確。 注 (1) 若( *)不成立，則計(jì)算不正確；但否命題不成立。 (2) 利用同樣的方法可以用來(lái)驗(yàn)證整數(shù)的加、減運(yùn)算的正確性。 2 剩余類(lèi)及完全剩

8、余系 定理1設(shè)m 0,則全體整數(shù)可分成 m個(gè)集合，記作：K,Ki, , Km 1，其 中Kr qm r |q Z, r 0,1, ,m 1,這些集合具有下列性 質(zhì)： (1) 每個(gè)整數(shù)必包含在而且 僅在上述的一個(gè)集合中 ； (2) 兩個(gè)整數(shù)同在一個(gè)集合的充分必要條件是對(duì)模 m同余。 證設(shè)a是任一整數(shù)，則必有 a mq ra，0 ra m， 于是由ra的存在性可知a g，由ra的唯一性可知a只能在 g中。 (2)設(shè)整數(shù) a,b Kr，貝U a mq1 r，b mq2 r，故 a b (mod m)。 反之，若a b (mod m),則a, b必處于同一 K r中。 定義1定理仲的K0,K1, ,

9、Km 1稱(chēng)為模m的剩余類(lèi)，一個(gè)剩余類(lèi) 中的任一 數(shù)稱(chēng)為它同類(lèi)數(shù)的剩余 。 若m個(gè)整數(shù)a0,a1, ,am 1中任何兩個(gè)數(shù)都不在同 一剩余類(lèi)，則a0,a1, ,am 1 稱(chēng)為模m的一個(gè)完全剩余系。 推論 m個(gè)整數(shù)作成模 m的一個(gè)完全剩余系的充分必要條件是它們對(duì)模m 兩兩不同余。 例如，下列序列都是模 m的完全剩余系: (1) 0,1,2, ,m 1;(最小非負(fù)完全剩余系) 0,m1, am a, ,(m 1)m (m 1); 0, m 1,( a 1) m a, ,( 1)m 1 m (m 1)； (4)當(dāng)m為偶數(shù)時(shí)， 1 m m 1, 5 1,0,1, m , 1； 2 2 2 m m m 2

10、 1, ,1,0,1, 1,； 2 2 2 當(dāng)m為奇數(shù)時(shí)， m 2 1 55 1,0,1, 5 1 1 。 2 (絕對(duì)最小完全剩余系) 定理2 設(shè)m Z ,(a,m)! b 乙 若 x通過(guò)模m的一個(gè)完全剩余系，則 ax b也通過(guò)模m的一個(gè)完全剩余系，即 若a0 ,a!, ,am勺是模m的完全剩余系， 則aao b, aai b, , aam 1 b也是模m的完全剩余系。 證 只需證明aao b,aa1 b, , aam 1 b兩兩不同余即可，采用 反證法。 設(shè)aai b aaj b (mod m) (i j)，貝U aai aaj (mod m)， 又(a, m) 1,于是 ai a j (m

11、od m) (i j),與已知矛盾， 故aa0 b, aa! b, , aam ! b也是模m的完全剩余系。 定理3 設(shè)mt,m2 Z , (m! ,m2) 1,而x , x2分別通過(guò)模mt, m2的完全剩 余系，則m2Xt m! x2也通過(guò)模m m2的完全剩余系。 證 因?yàn)閄!, x2分別通過(guò)m!, m2個(gè)整數(shù)，所以m2X! mx通過(guò)m2個(gè)整數(shù), 下證這m!m2個(gè)整數(shù)對(duì)模m! m2兩兩不同余。 設(shè) m2x m!X2 m2X!” m!X2(mod mm2),其中 xj,為，X2，X2分別是 所 通過(guò)的完全剩余系中的 數(shù)，貝U m2x! m2x! (mod m!), m!x2 m!x2 (mod

12、 m2), 又(mm?) ! 故 x! x! (mod m!), x2 x2 (mod m2)，這說(shuō)明 m2Xt m! x2 所通過(guò)的數(shù)兩兩不同余，因此，m2x! m!x2也通過(guò)模m!m2的完全剩余系。 例1設(shè)m 0(mod2), a1, ,am及b1, ,bm都是模m的完全剩余系，則 a b1, am bm不是模m的完全剩余系。 ,bm都是模m的完全剩余系， 所以 m ai m i m(m 1) m (mod m), m 同理b i 1 i 1 2 2 i 1 m m m_ 從而 佝 bi) ai m m bi 0 (mod m), i 1 i 1 i 122 m 若a b, ,am bm是

13、模m的完全剩余系， 則佝 i 1 因此, a1 b1, ,a mbm 不是模m的完全剩余系。 證：因?yàn)閍i, ,am及b , m (mod m), bi) 對(duì)任何正整數(shù) n， (mod m)，矛盾。 例2 證明 證： 考察i c, b 11 1 個(gè)數(shù)：1,11, 設(shè)b 1, c 111, k個(gè)1s個(gè) 1 設(shè) m Z ，(a,m) ax b 1 (m 1)。 2 存在著僅有數(shù)字1,0組成的數(shù)a，使得n|a。 ,111，它們對(duì)模n至少有兩個(gè)在同一同余 類(lèi)中, n 1個(gè) 1 c (mod n)，則 n |(b c) 111 000 a。 k s個(gè)1 s個(gè) 0 1, b Z， x通過(guò)模m的一個(gè)完全剩余

14、系, 證 因?yàn)閤通過(guò)模m的一個(gè)完全剩余系，所 以ax b通過(guò)模m的一個(gè)完全 剩余系，從而竺亠通過(guò)2,丄，匹J mm m m ax b 01 1 (m 1)。 2 3 簡(jiǎn)化剩余系與歐拉函數(shù) 定義1歐拉函數(shù)(a)是定義在正整數(shù)集上的 函數(shù)，它的值等于序列 0,1,2, ,a 1中與a互質(zhì)的數(shù)的個(gè)數(shù)。 注 若a是質(zhì)數(shù)，則 (a) a 1若a是合數(shù)，則 (a) a 1 定義2 如果一個(gè)模m的剩余類(lèi)中的數(shù)與 m互質(zhì)，則稱(chēng)它為一個(gè)與 模m互質(zhì) 的剩余類(lèi) 在與模m互質(zhì)的全部剩余類(lèi)中，從每一類(lèi)各取一數(shù)所作 成的數(shù)的集合稱(chēng)為 模m的一個(gè)簡(jiǎn)化剩余系。 定理1模m的剩余類(lèi)與模m互質(zhì)的充分必要條件是 此類(lèi)中有一數(shù)與m

15、互質(zhì)。 因此，與模m互質(zhì)的剩余類(lèi)的個(gè)數(shù)為 (m)，模m的每一簡(jiǎn)化剩余系是由 與m互質(zhì) 的(m)個(gè)對(duì)模m不同余的整數(shù)組成的。 證 設(shè)K0, K1, ,Km1是模m的全部剩余類(lèi)，若Kr與模m互質(zhì)，則(r, m) 1; 反之，若有 kr K r, (kr,m) 1,則對(duì)于 Kr 中任一數(shù) kr qm kr，有(kr,m) 1, 即Kr與模m互質(zhì)。 定理2 若a1, a2, , a (m)是(m)個(gè)與m互質(zhì)的整數(shù)，并且兩兩 對(duì)模m不同余， 則a1, a2, a (m)是模m的一個(gè)簡(jiǎn)化剩余系。 定理3 若(a,m) 1, x通過(guò)模m的簡(jiǎn)化剩余系，則ax也通過(guò)模m的簡(jiǎn)化剩 余系。 證 ax通過(guò)(m)個(gè)整數(shù)

16、，而且由(a,m) 1, (x,m) 1可知 (ax,m) 1, 若ax axj (mod m) (i j),則 x Xj (mod m) (i j),與已知矛盾， 故ax通過(guò)模m的簡(jiǎn)化剩余系。 定理4 設(shè)m1, m2 Z , (m1, m2) 1,而x1, x2分別通過(guò)模m1, m2的簡(jiǎn)化剩 余系，則m2Xt m x2也通過(guò)模mm?的簡(jiǎn)化剩余系。 證 由上一節(jié)定理3可知，若x ,x2分別通過(guò)模m-m?的完全剩余系，則 m2X! m/2也通過(guò)模m! m2的完全剩余系。下證當(dāng)Xt, x2分別通過(guò) 模, m2的簡(jiǎn) 化剩余系時(shí)，m2x. m.x2通過(guò)模m.m2的一個(gè)完全剩余系中一 切與m.m2互質(zhì)的

17、 整數(shù)。 一方面，由(x., m.) (x2,m2) (m.,m2) 1 可知(mzX.m.) 1, (m. x2, m2) 1, 于是(m2x1m1 x2, m1)1，(m1 x2m2x1, m2)1,從而(m2x1m1 x2, m1 m2)1， 另一方面，由(m2Xt m1x2,m1m2) 1 可知(m2Xt m1x2,m1) (m! x2 m2X!, m2) 1, 于是(mzymj (m/?,%) 1,從而(xmj (x2, m2) 1 推論設(shè)mm?Z ,(m!,m2)1,貝U(mtm2)(mJ(m2) 證 由定理4可知，若x1 ,x2分別通過(guò)模mt, m2的簡(jiǎn)化剩余系，貝U m2x1

18、m1 x2 通過(guò)模mm?的簡(jiǎn)化剩余系，即m2Xt m1 x2通過(guò) (mt m2)個(gè)整數(shù)。 另一方面， 由于x1通過(guò)(mJ個(gè)整數(shù)， x2通過(guò) (m2)個(gè)整數(shù), 因此， m2 x1m1 x 通過(guò) (m1) (m2)個(gè)整數(shù)。故 (mm?) (mJ (m2)。 定理5 設(shè) aP11 P22Pkk，則 (a) a 1 1 1 1 1 1 P1 P2 Pk 證先證 (P )P P S在模P的完全剩余系1,2, p中，與 P不互質(zhì) 的數(shù)為p,2p, ,P b共有 P 1 個(gè)，故(p ) pP ! 因此，(a) (P1 1) (P22) (Pkk) (P11P11 1)(P21P22 1) (Pkk k1 Pk ) 1 1 1 a 1 1 1 。 P1 P2 Pk 4歐拉定理費(fèi)馬定理 定理1 (Euler) 設(shè)m Z, m 1, (a, m) 1,則 a (m)1 (mod m)。 證 設(shè)幾，2, r (m)是模m的簡(jiǎn)化剩余系，貝U ar!, ar2, ,ar(m)也是模m的簡(jiǎn) 化剩余系，于是(arj(ar2) (ar(m) 亡r )(mod m), 即 a 5)(*2r (m)A2r (m) (modm),又(n ,m)(j,m) (r)，m)1, 故(rj2r (m), m) 1,從而 a (m) 1 (mod m) 推論(Fermat定理)若p是質(zhì)數(shù)，則ap a (mod p) 證