1、知识回顾剩余类定理剩余类定理 若若a,b,c为任意为任意3个整数，个整数，m为正整数，为正整数，且且(m,c)=1,则当则当acbc(modm)时，有时，有ab(modm)如果如果a,b,c,d是四个整数，且是四个整数，且ab(mod(mod m),),cd(mod m),),则有则有acbd(mod(mod m).).同余定理同余定理导入新课 上一讲我们讲了剩余类，剩余环上一讲我们讲了剩余类，剩余环并知道了它的运算法则并知道了它的运算法则.剩余类乘法：剩余类乘法：ab=b在整数集模在整数集模6的剩余环中的剩余环中24=8=289=72=0249=72=0当当n为素数时，模为素数时，模n的剩余
2、类环中无零因子的剩余类环中无零因子.0123401234由以前学的知识在填写模由以前学的知识在填写模5剩余环剩余环.0000000001234234413134221模模7剩余环剩余环07=.17=.27=.37=.47=.57=.67=.05=.15=.25=.35=.45=.03=.13=.23=.模模5剩余环剩余环模模3剩余环剩余环654320143201201对合数上述规律是对合数上述规律是否依然成立？否依然成立？找规律找规律观察一观察一第二讲第二讲 同余与同余方程同余与同余方程教学目标知识与能力知识与能力 1.理解费马小定理和欧拉定理的内理解费马小定理和欧拉定理的内容与证明过程容与证
3、明过程.2.能够运用费马小定理和欧拉定理能够运用费马小定理和欧拉定理简化数论中的一些计算问题简化数论中的一些计算问题.情感态度与价值观情感态度与价值观过程与方法过程与方法 1.通过举例对比总结费马小定理和通过举例对比总结费马小定理和欧拉定理的定义欧拉定理的定义.2.由以前学过的知识，对费马小定由以前学过的知识，对费马小定理和欧拉定理进行证明理和欧拉定理进行证明.认识费马小定理和欧拉定理的历史认识费马小定理和欧拉定理的历史及地位和作用及地位和作用.教学重难点1.欧拉函数的定义及性质欧拉函数的定义及性质.费马小定理和欧拉定理的证明过程，以及费马小定理和欧拉定理的证明过程，以及灵活运用这两个定理简化
4、数论中的一些计算灵活运用这两个定理简化数论中的一些计算.重点重点难点难点 2.欧拉定理、欧拉定理、Fermat小定理，循环小定理，循环小数的判定条件小数的判定条件.科普知识科普知识 瑞士著名的数学家欧拉瑞士著名的数学家欧拉,是数学史上的最多的数学家是数学史上的最多的数学家,他毕生从事数学研究他毕生从事数学研究,他的论他的论著几乎涉及著几乎涉及18世纪所以的数世纪所以的数学分支学分支.比如数学中的欧拉公比如数学中的欧拉公式式,欧拉方程欧拉方程.欧拉常数欧拉常数,欧拉欧拉方法方法.欧拉猜想等欧拉猜想等.欧拉晚年欧拉晚年不幸双目失明不幸双目失明，失明后的失明后的17年年，他还口述署了几本书和他还口述
5、署了几本书和约约400篇论篇论 费马生于法国南部费马生于法国南部，贡献包括贡献包括：与笛卡尔共与笛卡尔共同创立了解析几何；创同创立了解析几何；创造了作曲线切线的方法造了作曲线切线的方法.最有名的是费马大定理，最有名的是费马大定理，即不可能有满足即不可能有满足xn+yn=zn，n2的正整数的正整数x，y，z，n存在存在.费马小费马小定理是费马在定理是费马在1640年提年提出出.科普知识科普知识 通过观察一，我们得到模通过观察一，我们得到模7剩余环、模剩余环、模5剩余环、模剩余环、模3剩余环的规律，又由于剩余环的规律，又由于3、5、7都是素数，我们猜想：都是素数，我们猜想：设设m为素数，为素数，为
6、为任意整数，任意整数，1,1,1 mod.ma mam且则实例实例例一、例一、若若a=3，m=7，则，则am-11（modm）成立否）成立否.解：解：有以前的知识我们知道有以前的知识我们知道31 3（mod7）32 6（mod7）33 2（mod7）34 5（mod7）35 1（mod7）36 4（mod7）则：则：366！6！（！（mod7）.(1)又因为：又因为：(6!,5)=1 (2)所以：所以：361（mod7）即：即：am-11（modm）分析分析在例一的解析中我们用到了以前学习的知识在例一的解析中我们用到了以前学习的知识.(1)(1)中用到了等式左边相乘中用到了等式左边相乘等于等于
7、等式右边相乘等式右边相乘.(2)(2)中用到了同余的性质中用到了同余的性质“若若b c（modn），），且（且（，n）=1，则，则b c（modn）”.例一的解析符合费马小定理，下面我例一的解析符合费马小定理，下面我们用通式对费马小定理给予证明们用通式对费马小定理给予证明.设设 An=An=a,2,2a,3,3a,4,4a(p-1)-1)a 假设假设 AnAn中有中有2 2项项ma,na 被被p除以后余数是相同除以后余数是相同 得得 ma=na(mod(mod p)即即a(m-n)=0(mod)=0(mod p)因为因为 a和和p互质互质,所以所以 m-n=0(mod=0(mod p)又因为又
8、因为 m,n属于集合属于集合1,2,3.1,2,3.p-11且且m不等于不等于n 所以所以 m-n不可能是不可能是p的倍数的倍数.推出推出 和假设产生矛盾和假设产生矛盾.证明证明所以所以 An中任意中任意2项被项被p除得到的余数都不同除得到的余数都不同 又因为又因为对于任一个整数被对于任一个整数被p除以后的余数最多有除以后的余数最多有 p-1个个,分别是分别是1,2,3,.p-1 而数列而数列An中恰好有中恰好有p-1个数个数,所所以数列中的数被以数列中的数被p除以后的余数一定正好包含所有的除以后的余数一定正好包含所有的1,2,3,4,5.p-1 所以所以 a*2a*3a*(p-1)a=1*2
9、*3*4*(p-1)(mod p)对对两边进行化简两边进行化简,即可以得到即可以得到a(p-1)=1(mod p)巩固巩固1、11x1（mod3），则），则x=（）.2、1141（modx），则），则x=（）.3、116x（mod7），则），则x=（）.4、x61（mod7），），1-10之内之内x可能为可能为（）.521、2、3、4、5、6、8、9、101 我们看到在费马小定理中针对的是我们看到在费马小定理中针对的是m为为素数的情况，对于其它数能否找到类似的性素数的情况，对于其它数能否找到类似的性质呢，这就是下面要讲的质呢，这就是下面要讲的欧拉定理欧拉定理.拓展拓展 欧拉定理欧拉定理 设设m
10、为正整数，正整数，为任意整数，且（为任意整数，且（，m）=1，则，则 m m12.mm1 modm,.a个个素素 正正整整数数数数互互 的的的的其其中中表表示示，中中与与(1)令令 则则 Zn=S.因为因为 a 与与 n 互质，互质，xi(1 i (n)与与 n 互质，互质，所所以以 a*xi 与与 n 互质，所以互质，所以 a*xi mod n Zn.若若 i j，那么那么 xi xj，且由，且由 a,n互质可得互质可得 a*xi mod n a*xj mod n（消去律）（消去律）.naxnaxnaxn1 12 2S S =（m mo od d ）,（m mo od d ）,.,（m mo
11、 od d ）1212 n nZn=x,x,.,xZn=x,x,.,x证明：证明：对比等式的左右两端，因为对比等式的左右两端，因为 xi i (1 (1 i (n)与与 n 互质，所以互质，所以 a(n)(n)1 mod 1 mod n （消去律）（消去律）.anaaanananann1 12 21 12 21 12 2.(m m o od d)()().()(m m o od d )(m m o od d )(m m o od d ).(m m o od d)(m m o od d )nnnnx xxxxxxxx（2）费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-
12、精品课件精品课件ppt(ppt(实用版实用版)费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)课堂小结1、费马小定理、费马小定理 设设m为素数，为素数，a为任意整数，且（为任意整数，且（a，m）a则m-1m-11 m od.1 m od.m2、欧拉定理、欧拉定理 设设m为正整数，正整数，为任意整数，且（为任意整数，且（，m）=1，则，则 其中其中(m)表示表示1，2，m中与中与m互素的正整数的个数互素的正整数的个数.1 mod,mma 费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课
13、件ppt(ppt(实用版实用版)费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)针对性练习一、一、设设a，b，c，m是正整数，是正整数，m 1，(b,m)=1，并且并且b a 1(mod m)，b c 1(mod m)，记记d=(a,c)，则，则bd 1(mod m).解解 利用辗转相除法可以求出整数利用辗转相除法可以求出整数x，y，使得，使得ax cy=d，显然，显然xy 0，y 0，由式，由式(4)知知 1 b ax=b db cy=b d(b c)y b d(mod m)。若若 x 0，由式由式(4)知知 1 b c
14、y=b db ax=b d(ba)x b d(mod m)。费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)二、二、设设p p是素数，是素数，p p b bn n 1 1，n n N N，则下面的两，则下面的两个结论中至少有一个成立：个结论中至少有一个成立：()()p p b bd d 1 1对于对于n n的某个因数的某个因数d d 2，则，则()中的中的mod n可以改为可以改为mod 2n.解解 记记
15、d=(n,p 1)，由，由b n 1，b p 1 1(mod p)，及题一，有，及题一，有b d 1(mod p).费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)若若d d 2 2，则，则p p 1(mod 2)1(mod 2).由此及由此及结论结论()()，并利用同余的基本性质，得到，并利用同余的基本性质，得到 p p 1(mod 2 1(mod 2n n).).2|n若，这是一种解题方法这是一种解题
16、方法好好掌握吆好好掌握吆.费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)解解 由题二知由题二知 若若 p p 2 23535 1 1 则则 p p是是2 25 5 1=31 1=31或或2 27 7 1=127 1=127的素因数的素因数 或者或者 p p 1(mod 70)1(mod 70)由于由于 3131和和127127是素数是素数 并且并且 2 23535 1=31 1=31*127127*87
17、273918727391 所以所以，2 23535 1 1的另外的素因数的另外的素因数p p只可能在数列只可能在数列三、三、将将235 235 1=34359738367 1=34359738367分解因数分解因数.费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)71 71，211211，281281，(5)(5)中中 经检验经检验，得到，得到8727391=718727391=71*1229211229
18、21.显然显然，122921122921的素因数在的素因数在3131，127127或者数列或者数列(5)(5)中中 说明说明，122921122921不能被不能被3131和和127127整除，也不能被数整除，也不能被数 列列(5)(5)中的不超过中的不超过1 12 22 29 92 21 1 3 35 51 1的数整除，所以的数整除，所以122921是素数是素数于是于是 235 1=31*127*71*122921.费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版
19、人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)课堂练习1、313159被被7除的余数除的余数（）.6(mod 7)2、132005被被17除的余数除的余数（）.13(mod 17)3、17x1（mod5），则），则x=（）.A.5 B.6 C.4 D.7C4、5x1（mod6），则），则x=（）.A.5 B.6 C.4 D.2D费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)5、设设p，q是
20、两个不同的素数，证明：是两个不同的素数，证明：pq 1 qp 1 1(mod pq).由费马定理：由费马定理：qp 1 1(mod p)，pq 1 1(mod q)pq 1 qp 1 1(mod p)pq 1 qp 1 1(mod q)故故 pq 1 qp 1 1(mod pq).证明：证明：费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)612 1=(63 1)(63 1)(66 1)=5*43*7*3
21、1*46657 对于对于46657，它的素因数必为，它的素因数必为12k 1型，型，经检验的经检验的46657=13*37*97 故故612 1=5*7*13*31*37*43*97.6、将将612 1分解成素因数之积分解成素因数之积.解：解：费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)证明：因证明：因561=3*11*17，对于一切整数，对于一切整数a，(a,561)=1，有，有(a,3)=1，(a
22、,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).7、证明证明：对于任意的整数对于任意的整数a，(a,561)=1，都，都有有a560 1(mod 561)，但，但561是合数是合数.费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)再见再见费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)费马小定理和欧拉定理费马小定理和欧拉定理完整版完整版 人教版人教版1-1-精品课件精品课件ppt(ppt(实用版实用版)
