初等數(shù)論§3同余

1、第三章 同 余 同余是數(shù)論中的重要概念，同余理論是研究整數(shù)問題的重要工作之一.本章介紹同余的基本概念，剩余類和完全剩余系. 生活中我會經(jīng)常遇到與余數(shù)有關(guān)的問題，比如：某年級有將近400名學(xué)生。有一次演出節(jié)目排隊時出現(xiàn)：如果每8人站成一列則多余1人；如果改為每9人站成一列則仍多余1人；結(jié)果發(fā)現(xiàn)現(xiàn)成每10人結(jié)成一列，結(jié)果還是多余1人；聰名的你知道該年級共有學(xué)生多少名嗎？2022/8/131阜陽師范學(xué)院 數(shù)科院3.1同余的概念及其基本性質(zhì) 一、問題的提出1、今天是星期一，再過100天是星期幾？ 3、13511，13903，14589被自然數(shù)m除所得余數(shù) 相同，問m最大值是多少？ 2、31459265

2、3=2910 93995的橫線處漏寫了一個 數(shù)字，你能以最快的辦法補(bǔ)出嗎？2022/8/132阜陽師范學(xué)院 數(shù)科院二、同余的定義注：下面的三個表示是等價的：2022/8/133阜陽師范學(xué)院 數(shù)科院三、同余的性質(zhì)TH2設(shè)a，b，c，d，k是整數(shù)，并且 a b (mod m)， c d (mod m)， 則 a c b d (mod m)； ac bd (mod m); ak bk (mod m).注：TH1、TH2是最簡單、常用的性質(zhì)。2022/8/134阜陽師范學(xué)院 數(shù)科院2022/8/135阜陽師范學(xué)院 數(shù)科院TH4 下面的結(jié)論成立： a b (mod m)，dm，d 0 a b (mod

3、d)； a b (mod m)，k 0，kN ak bk (mod mk)； a b (mod mi )，1 i k a b (mod m1, m2, , mk)； a b (mod m) (a, m) = (b, m)； ac bc (mod m)，(c, m) = 1 a b (mod m);2022/8/136阜陽師范學(xué)院 數(shù)科院 a b (mod m)，dm，d 0 a b (mod d)； a b (mod m)，k 0，kN ak bk (mod mk)； a b (mod mi )，1 i k a b (mod m1, m2, , mk)； a b (mod m) (a, m)

4、= (b, m)；2022/8/137阜陽師范學(xué)院 數(shù)科院 ac bc (mod m)，(c, m) = 1 a b (mod m);注：若沒有條件(c, m) = 1，即為TH2的逆命題， 不能成立。反例：取m=6,c=2,a=20,b=23.2022/8/138阜陽師范學(xué)院 數(shù)科院2022/8/139阜陽師范學(xué)院 數(shù)科院四、一些整數(shù)的整除特征 (1) 3、9 的整除特征各位上的數(shù)字之和能被3（9）整除例1檢查5874192、435693能否被3（9）整除。2022/8/1310阜陽師范學(xué)院 數(shù)科院(2) 7、11、13 的整除特征注：一般地，求 被m除的余數(shù)時， 首先是求出正整數(shù)k，使得

5、10k 1或1 (mod m)， 2022/8/1311阜陽師范學(xué)院 數(shù)科院(2) 7、11、13 的整除特征特別地，由于 ，所以奇偶位差法 例2檢查637693、75312289能否被7（11，13）整除。由69363756，所以637693能被7整除，但不能被11，13整除， 當(dāng)然也可以由6+3-7+6-9+3=2知637693不能被11整除； 由75-312+28952，所以75312289能被13整除，但不能被7，11整除。 2022/8/1312阜陽師范學(xué)院 數(shù)科院2022/8/1313阜陽師范學(xué)院 數(shù)科院 求出整數(shù)k，使ak 1 (mod m)； 求出正整數(shù)r，r 0是偶數(shù)，a1,

6、 a2, , am與b1, b2, , bm都是模m的完全剩余系， 則a1 b1, a2 b2, , am bm不是模m的完全剩余系。 證 由1, 2, , m與a1, a2, , am都是模m的完全剩余系， 如果a1 b1, a2 b2, , am bm是模m的完全剩余系， 不可能！2022/8/1338阜陽師范學(xué)院 數(shù)科院例4 設(shè)miN（1 i n），則當(dāng)xi通過模mi（1 i n） 的完全剩余系時，x = x1 m1x2 m1m2x3 m1m2mn 1xn通過模m1m2mn的完全剩余系。證明 對n施行歸納法。當(dāng)n = 2時，由定理4知定理結(jié)論成立。假設(shè)定理結(jié)論當(dāng)n = k時成立， 即當(dāng)x

7、i（2 i k 1）分別通過模mi的完全剩余系時，y = x2 m2x3 m2m3x4 m2mkxk 1通過模m2m3mk 1的完全剩余系。 2022/8/1339阜陽師范學(xué)院 數(shù)科院y = x2 m2x3 m2m3x4 m2mkxk 1通過模m2m3mk 1的完全剩余系。 由定理4，當(dāng)x1通過模m1的完全剩余系， xi（2 i k 1）通過模mi的完全剩余系時，x1 m1y = x1 m1(x2 m2x3 m2mkxk 1)= x1 m1x2 m1m2x3 m1m2mkxk 1通過模m1m2mk 1的完全剩余系。 即結(jié)論對于n = k 1也成立。 2022/8/1340阜陽師范學(xué)院 數(shù)科院三

8、、與抽象代數(shù)的關(guān)系若將模m的剩余類作為元素，則 同余剩余類的相等，同余的運(yùn)算元素剩余類的運(yùn)算，剩余類的集合即是環(huán)。 特別地，當(dāng)m為合數(shù)時，就有： 非零的剩余類的乘積可能為零的剩余類，即存在零因子的環(huán)。上述環(huán)中所有與模m互質(zhì)的剩余類對乘法構(gòu)成群；當(dāng)m為質(zhì)數(shù)時，上述的環(huán)又可以構(gòu)成一個有限域。2022/8/1341阜陽師范學(xué)院 數(shù)科院2022/8/1342阜陽師范學(xué)院 數(shù)科院3.3 簡化剩余系與歐拉函數(shù) 一、基本概念定義1 設(shè)R是模m的一個剩余類，若有aR，使得(a, m)= 1，則稱R是模m的一個簡化剩余類。即與模m互質(zhì)的剩余類。 注：若R是模的簡化剩余類，則R中的數(shù)都與m互素。例如，模4的簡化剩

9、余類有兩個：R1(4) = , 7 , 3, 1 , 5 , 9 , ，R3(4) = , 5 , 1 , 3 , 7 , 11 , 。2022/8/1343阜陽師范學(xué)院 數(shù)科院定義2 對于正整數(shù)k，令函數(shù)(k)的值等于模k的所有簡化剩余類的個數(shù)，稱(k)為Euler函數(shù)。容易驗(yàn)證：(2) = 1，(3) = 2，(4) = 2，(7) = 6。注：(m)就是在m的一個完全剩余系中與m互素的 整數(shù)的個數(shù)，且 定義3 對于正整數(shù)m，從模m的每個簡化剩余類中 各取一個數(shù)xi，構(gòu)成一個集合x1, x2, ,x(m)， 稱為模m的一個簡化剩余系（或簡稱為簡化系）。 2022/8/1344阜陽師范學(xué)院

10、數(shù)科院注：由于選取方式的任意性，模m的簡化剩余系有無窮多個。例如，集合9, 5, 3, 1是模8的簡化剩余系； 集合1, 3, 5, 7也是模8的簡化剩余系. 集合1, 3, 5, 7稱為最小非負(fù)簡化剩余系。 2022/8/1345阜陽師范學(xué)院 數(shù)科院二、主要性質(zhì) 定理1 整數(shù)集合A是模m的簡化剩余系的充要條件是： A中含有(m)個整數(shù)； A中的任何兩個整數(shù)對模m不同余； A中的每個整數(shù)都與m互素。說明：簡化剩余系是某個完全剩余系中的部分元素構(gòu)成的集合，故滿足條件2； 由定義1易知滿足條件3；由定義3易知滿足條件1。2022/8/1346阜陽師范學(xué)院 數(shù)科院定理2 設(shè)a是整數(shù)，(a, m) =

11、 1，B = x1, x2, , x(m) 是模m的簡化剩余系，則集合 A = ax1, ax2, , ax(m) 也是模m的簡化剩余系。證明 顯然，集合A中有(m)個整數(shù)。 由于(a, m) = 1， 對于任意的xi（1 i (m)），xiB， 有(axi, m) = (xi, m) = 1。 故A中的每一個數(shù)都與m互素。 而且，A中的任何兩個不同的整數(shù)對模m不同余。 因?yàn)?，若有x , x B，使得 a x ax (mod m)，那么， x x (mod m)， 于是x = x 。 由以上結(jié)論及定理1可知集合A是模m的一個簡化系。 2022/8/1347阜陽師范學(xué)院 數(shù)科院注：在定理2的條件

12、下，若b是整數(shù)，集合ax1 b, ax2 b, , ax(m) b不一定是模m的簡化剩余系。 例如，取m = 4，a = 1，b = 1， 以及模4的簡化剩余系1, 3。但2，4不是模4的簡化剩余系。2022/8/1348阜陽師范學(xué)院 數(shù)科院定理3 設(shè)m1, m2N，(m1, m2) = 1，又設(shè)分別是模m1與m2的簡化剩余系， 則 A = m1y m2x；xX，yY 是模m1m2的簡化剩余系。證明 由第二節(jié)定理3推論可知， 若以X 與Y 分別表示 模m1與m2的完全剩余系，使得X X ，Y Y ， 則A = m1y m2x；xX ，yY 是模m1m2的完全 剩余系。 因此只需證明A 中所有與

13、m1m2互素的整數(shù)的集合R 即模m1m2的簡化剩余系是集合A。 2022/8/1349阜陽師范學(xué)院 數(shù)科院若m1y m2xR，則(m1y m2x, m1m2) = 1， 所以(m1y m2x, m1) = 1， 于是 (m2x, m1) = 1，(x, m1) = 1，xX。同理可得到y(tǒng)Y，因此m1y m2xA。 這說明R A。 另一方面，若m1y m2xA，則xX，yY， 即 (x, m1) = 1，(y, m2) = 1。由此及(m1, m2) = 1得到 (m2x m1y, m1) = (m2x, m1) = 1(m2x m1y, m2) = (m1y, m2) = 1。因?yàn)閙1與m2互

14、素，所以(m2x m1y, m1m2) = 1， 于是m2x m1yR。因此A R。 從而A = R。 2022/8/1350阜陽師范學(xué)院 數(shù)科院推論 設(shè)m, nN，(m, n) = 1，則(mn) = (m)(n)。證 由定理3知，若x,y分別通過m , n的簡化剩余系， 則my nx通過mn的簡化剩余系， 即有 my nx通過(mn)個整數(shù)。 另一方面，xnx通過(m)個整數(shù)， ymy通過(n)個整數(shù), 從而my nx通過(m) (n)個整數(shù)。故有 (mn) = (m)(n)。注：可以推廣到多個兩兩互質(zhì)數(shù)的情形。2022/8/1351阜陽師范學(xué)院 數(shù)科院定理4 設(shè)n是正整數(shù)，p1, p2,

15、 , pk是它的全部素因數(shù)， 證 設(shè)n的標(biāo)準(zhǔn)分解式是 由定理3推論得到 對任意的素數(shù)p， (p)等于數(shù)列1, 2, , p中與p互素的整數(shù)的個數(shù)， 從而定理得證。2022/8/1352阜陽師范學(xué)院 數(shù)科院注：由定理4可知，(n) = 1的充要條件是n = 1或2?？紤]有重素因子和沒有重素因子的情形。 三、應(yīng)用舉例注意：有重素因子時，上述不等式中等號不成立！2022/8/1353阜陽師范學(xué)院 數(shù)科院例1 設(shè)整數(shù)n 2，證明： 即在數(shù)列1, 2, , n中，與n互素的整數(shù)之和是 證 設(shè)在1, 2, , n中與n互素的個數(shù)是(n)，a1, a2, , a(n)，(ai, n) = 1，1 ai n

16、1，1 i (n)，則 (n ai, n) = 1，1 n ai n 1，1 i (n)，因此，集合a1, a2, , a(n)故 a1 a2 a(n) = (n a1) (n a2) (n a(n)，從而，2(a1 a2 a(n) = n(n)，因此 a1 a2 a(n) 與集合n a1, n a2, , n a(n)是相同的，2022/8/1354阜陽師范學(xué)院 數(shù)科院例2 設(shè)nN，證明：1) 若n是奇數(shù)，則(4n) = 2(n)；的充要條件是n = 2k，kN；的充要條件是n = 2k3l，k, lN；4) 若6n，則(n) 5) 若n 1與n 1都是素數(shù)，n 4，則(n) 2022/8/

17、1355阜陽師范學(xué)院 數(shù)科院1) 若n是奇數(shù)，則(4n) = 2(n)；(4n) = (22n)= (22)(n)= 2(n)TH42022/8/1356阜陽師范學(xué)院 數(shù)科院的充要條件是n = 2k，kN；若n = 2k， 若(n) = 設(shè)n = 2kn1， 由 (n) = (2kn1) = (2k)(n1) =2k 1(n1) 所以n1 = 1，即n = 2k；2022/8/1357阜陽師范學(xué)院 數(shù)科院的充要條件是n = 2k3l，k, lN；設(shè) n = 2k3ln1， 所以n1 = 1，即n = 2k3l；若 n = 2k3l，則 (n) = (2k)(3l)2022/8/1358阜陽師范

18、學(xué)院 數(shù)科院4) 若6n，則(n) 設(shè) n = 2k3ln1， 則 (n) = (2k)(3l)(n1) 2022/8/1359阜陽師范學(xué)院 數(shù)科院5) 若n 1與n 1都是素數(shù)，n 4，則(n) 因?yàn)閚 4，且n 1與n 1都是奇素數(shù)， 所以n是偶數(shù)，且n 1 3.所以n 1與n 1都不等于3，所以3n，由結(jié)論4，也不能被3整除，因此6n。即可得到結(jié)論5。若6n，則(n) 2022/8/1360阜陽師范學(xué)院 數(shù)科院例3 證明：若m, nN，則(mn) = (m, n)(m, n)；證： 顯然mn與m, n有相同的素因數(shù)， 設(shè)它們是pi（1 i k），則由此兩式及mn = (m, n)m, n

19、即可得證。2022/8/1361阜陽師范學(xué)院 數(shù)科院2022/8/1362阜陽師范學(xué)院 數(shù)科院3.4歐拉定理 費(fèi)馬定理及其對循環(huán)小數(shù)的應(yīng)用 本節(jié)主要通過應(yīng)用簡化剩余系的性質(zhì)證明數(shù)論中的兩個重要定理，歐拉定理和費(fèi)馬定理，并說明其在理論和解決實(shí)際問題中的應(yīng)用。2022/8/1363阜陽師范學(xué)院 數(shù)科院一、兩個基本定理定理1Euler 設(shè) m是正整數(shù)，(a, m) = 1， 則 am) 1 (mod m).證明： 設(shè)x1, x2, , x(m)是模m的一個簡化剩余系， 則ax1, ax2, , ax(m)也是模m的簡化剩余系， 所以 ax1ax2ax(m) x1x2 x(m) (mod m)，即 a

20、(m)x1x2x(m) x1x2, x(m) (mod m). 得 (x1x2x(m), m) = 1， 所以 a(m) 1 (mod m). 2022/8/1364阜陽師范學(xué)院 數(shù)科院定理2(Fermat) 設(shè)p是素數(shù)， a p a (mod p)。 注：Fermat定理即是歐拉定理的推論。證： 由于p是素數(shù)， 若 (a, p) 1， 則由定理1得到 a p 1 1 (mod p) a p a (mod p) 若(a, p) 1，則pa， 所以 a p 0 a (mod p) am) 1 (mod m)2022/8/1365阜陽師范學(xué)院 數(shù)科院二、定理的應(yīng)用舉例例1 求313159被7除的余

21、數(shù)。解：313159所以由歐拉定理得 am) 1 (mod m)從而 5159= (56)2653 53 (mod 7) 53 = 255 45 6 (mod 7)。即 313159被7除的余數(shù)為6。2022/8/1366阜陽師范學(xué)院 數(shù)科院例2 設(shè)n是正整數(shù)，則5 1n 2n 3n 4n的充要條件是4n。證： 因?yàn)?5) = 4， 由定理1得 am) 1 (mod m)k4 1 (mod 5)，1 k 4。因此，記n = 4q r，0 r 3， 則 1n 2n 3n 4n 1r 2r 3r 4r 1r 2r (2)r (1)r (mod 5). 用 r = 0，1，2，3分別代入即可得出結(jié)論

22、。2022/8/1367阜陽師范學(xué)院 數(shù)科院例3 設(shè)x1, x2, , x(m)是模m的簡化剩余系， 則 (x1x2x(m)2 1 (mod m).證： 記P = x1x2x(m)， 則(P, m) = 1. 1 i (m)，則y1, y2, , y(m)也是模m的簡化剩余系， 再由Euler定理得證.am) 1 (mod m)2022/8/1368阜陽師范學(xué)院 數(shù)科院例4 設(shè)a，b，c，m是正整數(shù)，m 1，(b, m) = 1， 并且 b a 1 (mod m)，b c 1 (mod m)， 記d = (a, c)，則bd 1 (mod m)。證 利用輾轉(zhuǎn)相除法可以求出整數(shù)x，y，使得ax

23、cy = d， 顯然xy 0，y 0， 則 1 b ax= b db cy= b d(b c) y b d (mod m)若x 0， 則 1 b cy= b db ax= b d(ba) x b d (mod m)。2022/8/1369阜陽師范學(xué)院 數(shù)科院例5 設(shè)n是正整數(shù)，記Fn = 證： 容易驗(yàn)證，當(dāng)n 4時Fn是素數(shù)， 由Fermat定理可知結(jié)論顯然成立。a p a (mod p)。 當(dāng)n 5時，有n 1 2n， 其中Q1與Q2是整數(shù)， 2022/8/1370阜陽師范學(xué)院 數(shù)科院補(bǔ)充說明我們已經(jīng)知道，F(xiàn)5是合數(shù)，因此例5表明， Fermat定理的逆定理不成立。 設(shè)p是素數(shù)， a p a

24、 (mod p)。 即若有整數(shù)a，(a, n) = 1，使得 a n 1 1 (mod n)， 并不能保證n是素數(shù)。 例5 設(shè)n是正整數(shù)，記Fn = Fermat定理2022/8/1371阜陽師范學(xué)院 數(shù)科院例6 如果今天是星期一，再過101010天是星期幾？即得：再過101010天是星期五。2022/8/1372阜陽師范學(xué)院 數(shù)科院三、在分?jǐn)?shù)與小數(shù)互化中的應(yīng)用 有理數(shù)，即有限小數(shù)和無限循環(huán)小數(shù)，可以用分?jǐn)?shù)來表示。利用歐拉定理可以解決分?jǐn)?shù)、小數(shù)的轉(zhuǎn)化問題。定義 如果對于一個無限小數(shù) 則稱之為循環(huán)小數(shù)，并簡記為 注：若找到的t是最小的，則稱 為循環(huán)節(jié)；t稱為循環(huán)節(jié)的長度；若最小的s0， 則稱該小

25、數(shù)為純循環(huán)小數(shù)，否則為混循環(huán)小數(shù)。2022/8/1373阜陽師范學(xué)院 數(shù)科院定理3 有理數(shù) 能表示為純循環(huán)小數(shù) 即：分母不含質(zhì)因數(shù)2或5。2022/8/1374阜陽師范學(xué)院 數(shù)科院定理3 有理數(shù) 能表示為純循環(huán)小數(shù) (b, 10) = 1 由Euler定理可知，有正整數(shù)k，使得10k 1 (mod b)，0 k (b)，因此存在整數(shù)q使得 而且ak, , a1不能都等于0，也不能都等于9。 = 0.akak 1a1akak 1a1 。2022/8/1375阜陽師范學(xué)院 數(shù)科院定理4 設(shè)a與b是正整數(shù)，0 a b，(a, b) = 1， 并且 b = 25b1，(b1, 10) = 1，b1 1

26、， 此處與是不全為零的正整數(shù)， 其中不循環(huán)的位數(shù)碼個數(shù)是 = max .則 可以表示成混循環(huán)小數(shù)，證明：不妨假設(shè) = ， 其中0 a1 b1，0 M 10， 且(a1, b1) = (2 a Mb1, b1) = (2 a, b1) = (a, b1) = 1。因此，由定理3， 可以表示成純循環(huán)小數(shù)： 2022/8/1376阜陽師范學(xué)院 數(shù)科院M = m110 1 m210 2 m（0 mi 9，1 i ）， 下面說明，上式中的是最小的不循環(huán)位數(shù)碼的個數(shù)。 若不然，設(shè)又有正整數(shù)， 2022/8/1377阜陽師范學(xué)院 數(shù)科院由定理3有 其中b1 ， 10ab1 = ba。 上式右端可以被5 整除， 但是(a, 10) = 1，(b1, 10) = 1， 所以5， 。 這就證明了不循環(huán)位數(shù)碼