初等數(shù)論三-課件

1、初等數(shù)論(三) Number Theory（Chap3）信陽(yáng)職業(yè)技術(shù)學(xué)院 夏子厚第三章 同余性質(zhì)教學(xué)目的和要求（1）熟練掌握同余的基本概念及性質(zhì)。（2）熟練掌握剩余類(lèi)、完全剩余系、簡(jiǎn)化剩余系和歐拉函數(shù)的概念及其性質(zhì)。（3）熟練掌握歐拉定理、費(fèi)馬定理和解某些同余問(wèn)題。本章是初等數(shù)論的核心內(nèi)容，是學(xué)生應(yīng)必須掌握的基礎(chǔ)知識(shí)。第一節(jié) 同余的概念及其基本性質(zhì)定義1 給定正整數(shù)m，如果用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)。第一節(jié) 同余的概念及其基本性質(zhì)定理1 下面的三個(gè)敘述是等價(jià)

2、的：() a b (mod m)；()存在整數(shù)q，使得a = b qm；()存在整數(shù)q1，q2，使得 a = q1m r， b = q2m r，0 r 0，kN ak bk (mod mk)；a b (mod mi )，1 i k a b (mod m1, m2, , mk)；(9) a b (mod m)，dm，d 0 a b (mod d)；(10) a b (mod m) (a, m) = (b, m)第一節(jié) 同余的概念及其基本性質(zhì)例1 設(shè)N =是整數(shù)N的十進(jìn)制表示，即N = an10n an 110n 1 a110 a0 ，則 (1) 3N 3 (2) 9N 9 (3) 7、11、13

3、N 7、11、13 第一節(jié) 同余的概念及其基本性質(zhì)證 由100 1，101 1，102 1， (mod 3)及推論3.3可知N = (mod 3)，由上式可得到結(jié)論(1)。同理可得（2）。 為了證明結(jié)論(3)，把N寫(xiě)成 N =同理可得（3）。 第一節(jié) 同余的概念及其基本性質(zhì)例2 求N = 被7整除的條件，并說(shuō)明1123456789能否被7整除。解 由得7N 7由于789 456 123 1 = 455，7455，所以71123456789。第一節(jié) 同余的概念及其基本性質(zhì)例3 說(shuō)明 是否被641整除。解 依次計(jì)算同余式22 4，24 16，28 256，216 154，232 1 (mod 64

4、1)。因此 0 (mod 641)，即641 第一節(jié) 同余的概念及其基本性質(zhì)例4 求(25733 46)26被50除的余數(shù)。解 利用定理4有(25733 46)26 (733 4)26 = 7(72)16 426 7( 1)16 426 = (7 4)26 326 = 3(35)5 3(7)5 = 37(72)2 21 29 (mod 50)，即所求的余數(shù)是29。第一節(jié) 同余的概念及其基本性質(zhì)例5 求n = 的個(gè)位數(shù)。解 我們有71 3，72 1，74 1 (mod 10)，因此，若77 r (mod 4)，則n = 74m+r (74)m7r 7r (mod 10)。 現(xiàn)在 77 (1)7

5、1 3 (mod 4)，所以n = 73 (3)3 7 3 (mod 10)，即n的個(gè)位數(shù)是3。第一節(jié) 同余的概念及其基本性質(zhì)注：一般地，若求 對(duì)模m的同余，可分以下步驟進(jìn)行：() 求出整數(shù)k，使ak 1 (mod m)；() 求出正整數(shù)r，r 1，并且(n 1)! 1 (mod n)，則n是質(zhì)數(shù)。其實(shí)若不然，設(shè)n = n1n2，1 n1 1，(a, m) = 1，x1, x2, , x(m)是模m的簡(jiǎn)化剩余系，證明：其中x表示x的小數(shù)部分。第四節(jié) 歐拉定理與費(fèi)馬定理本節(jié)中所介紹的歐拉定理，在理論和應(yīng)用兩個(gè)方面都是很重要的。 歐拉定理 設(shè)m是正整數(shù)，(a, m) = 1，則 am) 1 (mo

6、d m)。證明 由定理3，設(shè)x1, x2, , x(m)是模m的一個(gè)簡(jiǎn)化剩余系，則ax1, ax2, , ax(m)也是模m的簡(jiǎn)化剩余系，因此ax1ax2ax(m) x1x2 x(m) (mod m)，即： a(m)x1x2x(m) x1x2, x(m) (mod m)。 由于(x1x2x(m), m) = 1，所以 a(m) 1 (mod m)。第四節(jié) 歐拉定理與費(fèi)馬定理費(fèi)馬定理 設(shè)p是質(zhì)數(shù)，則對(duì)于任意的整數(shù)a，有 a p a (mod p)。證明： 若(a, p) 1，則由歐拉定理知a p 1 1 (mod p) a p a (mod p)；若(a, p) 1，則pa，所以 a p 0 a

7、 (mod p)。第四節(jié) 歐拉定理與費(fèi)馬定理注：Fermat定理的逆定理不成立。如對(duì)于任意的整數(shù)a，(a, 561) = 1，都有a560 1 (mod 561)，但561是合數(shù)。事實(shí)上，由561 = 31117， (a, 561) = 1，有(a, 3) = 1，(a, 11) = 1，(a, 17) = 1， 又由費(fèi)馬定理可得a560 = (a2)280 1 (mod 3)，a560 = (a10)56 1 (mod 11)，a560 = (a16)35 1 (mod 17)，故a560 1 (mod 561)。第四節(jié) 歐拉定理與費(fèi)馬定理根據(jù)歐拉定理，當(dāng)(a, m) = 1時(shí)，總能找到x=

8、(m)，使得ax 1 (mod m)。但(m)并不是使ax 1 (mod m)成立的自然數(shù)x中的最小數(shù)。如a=5，m=8時(shí)，521(mod8)， 這里2 （8）=4。第四節(jié) 歐拉定理與費(fèi)馬定理例1 證明：17771885 27 (mod 41) 證明：因41是質(zhì)數(shù)，由歐拉定理有177740 1(mod 41)。又1885=4740+5，所以17771885 =17774740 17775 =（177740）47 17775 17775 145 1962 14 322 14 27 (mod 41)。第四節(jié) 歐拉定理與費(fèi)馬定理例2 求62011除以14的非負(fù)最小余數(shù)。解：由（6，14）=2知，它們

9、不互質(zhì)，從而不能直接利用歐拉定理求解。注意到62011 =2362010 ，14=27，7為質(zhì)數(shù)，由62010 (-1)2010 1 (mod 7)及同余性質(zhì)知，362010 3 (mod 7)，進(jìn)而得到2362010 23 (mod 14)，故62011 6 (mod 14)。第四節(jié) 歐拉定理與費(fèi)馬定理例3 求證：對(duì)于任意整數(shù)， 是一個(gè)整數(shù)。證明：令f(x) = ，則只需證15 f(x) = 是15的倍數(shù)即可。第四節(jié) 歐拉定理與費(fèi)馬定理由3，5是質(zhì)數(shù)及Fetmat小定理得x5 x (mod 5) ， x3 x (mod 5) ，則而（3，5）=1，故 即15 f(x)是15的倍數(shù)。所以f(x)是整數(shù) 第四節(jié) 歐拉定理與費(fèi)馬定理例4 設(shè)(a, m) = 1，d0是使 a d 1 (mod m)成立的最小正整數(shù)，則() d0(m)；() 對(duì)于任意的i，j，0 i, j d0 1， i j，有 a i a j (mod m)。 (1)第四節(jié) 歐拉定理與費(fèi)馬定理解 () 由Euler定理，d0 (m)，因此，由帶余數(shù)除法，有(m) = qd0 r，qZ，q 0，0 r d0。因此，1 (mod m)，即整數(shù)r滿足a r 1 (mod m)，0 r j。因?yàn)?a, m) = 1，所以ai j 0 (mod m)，0 i j d0。