初等数论三-课件.ppt

1、初等数论初等数论(三三)Number Theory（Chap3）信阳职业技术学院 夏子厚第三章第三章 同余性质同余性质 教学目的和要求教学目的和要求（1）熟练掌握同余的基本概念及性质。（2）熟练掌握剩余类、完全剩余系、简化剩余系和欧拉函数的概念及其性质。（3）熟练掌握欧拉定理、费马定理和解某些同余问题。本章是初等数论的核心内容，是学生应必须掌握的基础知识。第一节第一节 同余的概念及其基本性质同余的概念及其基本性质 定义定义1 给定正整数m，如果用m去除任意的两个整数a与b所得的余数相同，则称a与b对于模m同余。记为 a b(mod m)，如果余数不同，则称a与b对于模m不同余。记为a b(mo

2、d m)。第一节第一节 同余的概念及其基本性质同余的概念及其基本性质 定理定理1 下面的三个叙述是等价的：()a b(mod m)；()存在整数q，使得a=b qm；()存在整数q1，q2，使得 a=q1m r，b=q2m r，0 r 0，k N ak bk(mod mk)；(8)a b(mod mi)，1 i k a b(mod m1,m2,mk)；(9)a b(mod m)，d m，d 0 a b(mod d)；(10)a b(mod m)(a,m)=(b,m)第一节第一节 同余的概念及其基本性质同余的概念及其基本性质 例例1 设N=是整数N的十进制表示，即 N=an10n an 110n

3、 1 a110 a0，则 (1)3N 3 (2)9N 9 (3)7、11、13N 7、11、13 niia0|niia0|345012aaaaaa第一节第一节 同余的概念及其基本性质同余的概念及其基本性质证 由100 1，101 1，102 1，(mod 3)及推论3.3可知 N=(mod 3)，由上式可得到结论(1)。同理可得（2）。为了证明结论(3)，把N写成 N=同理可得（3）。niiniiiaa00103345001201211010aaaaaaaaaann第一节第一节 同余的概念及其基本性质同余的概念及其基本性质 例例2 求N=被7整除的条件，并说明1123456789能否被7整除。

4、解解 由由 得7N 7 由于789 456 123 1=455，7455，所以71123456789。0121aaaann，)7(mod1010678345012334500120121aaaaaaaaaaaaaaaaaaaNnn678345012aaaaaaaaa第一节第一节 同余的概念及其基本性质同余的概念及其基本性质 例例3 说明 是否被641整除。解解 依次计算同余式 22 4，24 16，28 256，216 154，232 1(mod 641)。因此 0(mod 641)，即641 125212521252第一节第一节 同余的概念及其基本性质同余的概念及其基本性质 例例4 求(25

5、733 46)26被50除的余数。解解 利用定理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)，即所求的余数是29。第一节第一节 同余的概念及其基本性质同余的概念及其基本性质 例例5 求n=的个位数。解解 我们有71 3，72 1，74 1(mod 10)，因此，若77 r(mod 4)，则n=74m+r (74)m7r 7r(mod 10)。现在 77 (1)7 1 3(mod 4)，所以 n=73 (3)3 7 3(mod 10)，即n的个位数是3。

6、777777777777777第一节第一节 同余的概念及其基本性质同余的概念及其基本性质 注注：一般地，若求 对模m的同余，可分以下步骤进行：()求出整数k，使ak 1(mod m)；()求出正整数r，r 1，并且，并且(n 1)!1(mod n)，则，则n是质数。其实若不然，设是质数。其实若不然，设n=n1n2，1 n1 1，(a,m)=1，x1,x2,x(m)是模m的简化剩余系，证明：其中x表示x的小数部分。(n)211),(1ninini21)(1)(21miimmax第四节第四节 欧拉定理与费马定理欧拉定理与费马定理 本节中所介绍的欧拉定理，在理论和应用两个方面都是很本节中所介绍的欧拉

7、定理，在理论和应用两个方面都是很重要的。重要的。欧拉定理欧拉定理 设设m是正整数，是正整数，(a,m)=1，则，则 a m)1(mod m)。证明证明 由定理由定理3，设，设x1,x2,x(m)是模是模m的一个简化剩余的一个简化剩余系，则系，则ax1,ax2,ax(m)也是模也是模m的简化剩余系，因此的简化剩余系，因此 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)。第四节第四节 欧拉定理与费马定理欧拉定理与费马定理 费马定理费马定理 设设p是

8、质数，则对于任意的整是质数，则对于任意的整数数a，有，有 a p a(mod p)。证明：证明：若若(a,p)1，则由欧拉定理知，则由欧拉定理知 a p 1 1(mod p)a p a(mod p)；若若(a,p)1，则，则p a，所以，所以 a p 0 a(mod p)。第四节第四节 欧拉定理与费马定理欧拉定理与费马定理 注：注：Fermat定理的逆定理不成立。如定理的逆定理不成立。如对于任意的整数对于任意的整数a，(a,561)=1，都有，都有a560 1(mod 561)，但，但561是合数。是合数。事实上，由事实上，由561=3 11 17，(a,561)=1，有有(a,3)=1，(a

9、,11)=1，(a,17)=1，又又由费马定理可得由费马定理可得a560=(a2)280 1(mod 3)，a560=(a10)56 1(mod 11)，a560=(a16)35 1(mod 17)，故，故a560 1(mod 561)。第四节第四节 欧拉定理与费马定理欧拉定理与费马定理 根据欧拉定理，当根据欧拉定理，当(a,m)=1时，总能找时，总能找到到x=(m)，使得，使得ax 1(mod m)。但。但(m)并并不是使不是使ax 1(mod m)成立的自然数成立的自然数x中的最中的最小数。小数。如如a=5，m=8时，时，52 1(mod8)，这里这里2 （8）=4。第四节第四节 欧拉定理

10、与费马定理欧拉定理与费马定理 例例1 证明：证明：17771885 27(mod 41)证明：因证明：因41是质数，由欧拉定理有是质数，由欧拉定理有177740 1(mod 41)。又。又1885=4740+5，所以所以 17771885=17774740 17775 =（177740）47 17775 17775 145 1962 14 322 14 27(mod 41)。第四节第四节 欧拉定理与费马定理欧拉定理与费马定理 例例2 求求62011除以除以14的非负最小余数。的非负最小余数。解：由（解：由（6，14）=2知，它们不互质，从知，它们不互质，从而不能直接利用欧拉定理求解。注意到而不

11、能直接利用欧拉定理求解。注意到 62011=2362010，14=27，7为质数，为质数，由由62010 (-1)2010 1(mod 7)及同余性质知，及同余性质知，362010 3(mod 7)，进而得到，进而得到2362010 23(mod 14)，故故62011 6(mod 14)。第四节第四节 欧拉定理与费马定理欧拉定理与费马定理 例例3 求证：对于任意整数，是一个整数。证明：令f(x)=，则只需证15 f(x)=是15的倍数即可。xxx157315135xxx157315135xxx75335第四节第四节 欧拉定理与费马定理欧拉定理与费马定理 由由3，5是质数及是质数及Fetmat

12、小定理得小定理得 x5 x(mod 5)，x3 x(mod 5)，则，则 而（而（3，5）=1，故，故 即即15 f(x)是是15的倍数。所以的倍数。所以f(x)是整数是整数 )5(mod07375335xxxxx)3(mod0275335xxxxx)15(mod075335xxx第四节第四节 欧拉定理与费马定理欧拉定理与费马定理 例例4 设(a,m)=1，d0是使 a d 1(mod m)成立的最小正整数，则()d0(m)；()对于任意的i，j，0 i,j d0 1，i j，有 a i a j(mod m)。(1)第四节第四节 欧拉定理与费马定理欧拉定理与费马定理 解解 ()由Euler定理，d0 (m)，因此，由带余数除法，有(m)=qd0 r，qZ，q 0，0 r d0。因此，1 (mod m)，即整数r满足 a r 1(mod m)，0 r j。因为(a,m)=1，所以 ai j 0(mod m)，0 i j d0。这与d0的定义矛盾，所以式(1)必成立。第四节第四节 欧拉定理与费马定理欧拉定理与费马定理 思考与练习思考与练习3.4 1、如果今天是星期一，问从今天起再过 天是星期几？2、求（1237156+34）28被111除的余数。3、证明：（a+b）pap+bp(mod p)。4、设p，q是两个不同的素数，证明：pq 1 qp 1 1(mod pq)。101010