《费马小定理和欧拉定理》完整版 人教版1课件

知识回顾剩余类定理

若a,b,c为任意3个整数，m为正整数，且(m,c)=1,则当ac≡bc(modm)时，有a≡b(modm)

如果a,b,c,d是四个整数，且a≡b(modm),c≡d(mod

m),则有ac≡bd(modm).

同余定理知识回顾剩余类定理若a,b,c为任意3个整数，m为正1导入新课

上一讲我们讲了剩余类，剩余环并知道了它的运算法则.剩余类乘法：[a][b]=[ɑb]在整数集模6的剩余环中[2][4]=[8]=[2][8][9]=[72]=[0][2][4][9]=[72]=[0]导入新课上一讲我们讲了剩余类，剩余环并知道了2当n为素数时，模n的剩余类环中无零因子.·[0][1][2][3][4][0][1][2][3][4]由以前学的知识在填写模5剩余环.[0][0][0][0][0][0][0][0][0][1][2][3][4][2][3][4][4][1][3][1][3][4][2][2][1]当n为素数时，模n的剩余类环中无零因子.·[0][1][2]3模7剩余环[07]=

.[17]=

.[27]=

.[37]=

.[47]=

.[57]=

.[67]=

.[05]=

.[15]=

.[25]=

.[35]=

.[45]=

.[03]=

.[13]=

.[23]=

.模5剩余环模3剩余环[6][5][4][3][2][0][1][4][3][2][0][1][2][0][1]对合数上述规律是否依然成立？找规律观察一模7剩余环[07]=4第三节费马小定理和欧拉定理第二讲同余与同余方程第三节费马小定理和欧拉定理第二讲同余与同余方程5教学目标知识与能力1.理解费马小定理和欧拉定理的内容与证明过程.2.能够运用费马小定理和欧拉定理简化数论中的一些计算问题.教学目标知识与能力1.理解费马小定理和欧拉定6情感态度与价值观过程与方法1.通过举例对比总结费马小定理和欧拉定理的定义.2.由以前学过的知识，对费马小定理和欧拉定理进行证明.

认识费马小定理和欧拉定理的历史及地位和作用.情感态度与价值观过程与方法1.通过举例对比总7教学重难点1.欧拉函数的定义及性质.

费马小定理和欧拉定理的证明过程，以及灵活运用这两个定理简化数论中的一些计算.

重点难点2.欧拉定理、Fermat小定理，循环小数的判定条件.教学重难点1.欧拉函数的定义及性质.费马小定理和欧8科普知识

瑞士著名的数学家欧拉,是数学史上的最多的数学家,他毕生从事数学研究,他的论著几乎涉及18世纪所以的数学分支.比如数学中的欧拉公式,欧拉方程.欧拉常数,欧拉方法.欧拉猜想等.欧拉晚年不幸双目失明，失明后的17年，他还口述署了几本书和约400篇论．科普知识瑞士著名的数学家欧拉,是数学史上的最9费马生于法国南部

，贡献包括：与笛卡尔共同创立了解析几何；创造了作曲线切线的方法

.最有名的是费马大定理，即不可能有满足xn+yn=zn，n>2的正整数x，y，z，n存在.费马小定理是费马在1640年提出.科普知识费马生于法国南部，贡献包括：与笛卡尔共同创10

通过观察一，我们得到模7剩余环、模5剩余环、模3剩余环的规律，又由于3、5、7都是素数，我们猜想：

费马小定理设m为素数，ɑ为任意整数，通过观察一，我们得到模7剩余环、模5剩余环、模3剩余11实例例一、若a=3，m=7，则am-1≡1（modm）成立否.解：有以前的知识我们知道3×1≡3（mod7）3×2≡6（mod7）3×3≡2（mod7）3×4≡5（mod7）3×5≡1（mod7）3×6≡4（mod7）则：36×6！≡6！（mod7）.(1)又因为：(6!,5)=1(2)所以：36≡1（mod7）即：am-1≡1（modm）实例例一、若a=3，m=7，则am-1≡1（modm）成立否12分析在例一的解析中我们用到了以前学习的知识.(1)中用到了等式左边相乘等于等式右边相乘.(2)中用到了同余的性质“若ɑb≡ɑc（modn），且（ɑ，n）=1，则b≡c（modn）”.

例一的解析符合费马小定理，下面我们用通式对费马小定理给予证明.分析在例一的解析中我们用到了以前学习的知识.(1)中用到了13设An=a,2a,3a,4a……(p-1)a

假设An中有2项ma,na

被p除以后余数是相同得ma=na(modp)即a(m-n)=0(modp)因为a和p互质,所以m-n=0(modp)又因为m,n属于集合{1,2,3..p-1}且m不等于n

所以m-n不可能是p的倍数.推出和假设产生矛盾.证明设An=a,2a,3a,4a……(p-1)a14所以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*3*4…*(p-1)(modp)对两边进行化简,即可以得到a(p-1)=1(modp)所以An中任意2项被p除得到的余数都不同15巩固1、11x≡1（mod3），则x=（）.2、114≡1（modx），则x=（）.3、116≡x（mod7），则x=（）.4、x6≡1（mod7），1-10之内x可能为（）.521、2、3、4、5、6、8、9、101巩固1、11x≡1（mod3），则x=（）.16

我们看到在费马小定理中针对的是m为素数的情况，对于其它数能否找到类似的性质呢，这就是下面要讲的欧拉定理.拓展

欧拉定理

设m为正整数，ɑ为任意整数，且（ɑ，m）=1，则我们看到在费马小定理中针对的是m为素数的情况，对于其17(1)

令

则Zn=S.

①因为a

与n

互质，xi(1≤i≤φ(n))与n

互质，所以a*xi

与n

互质，所以a*ximodn∈Zn.

②若i

≠j

，那么xi≠xj，且由a,n互质可得a*ximodn≠a*xjmodn

（消去律）.证明：(1)令证明：18

对比等式的左右两端，因为xi(1≤i≤φ(n))与n

互质，所以aφ(n)≡1modn

（消去律）.

（2）《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)对比等式的左右两端，因为xi(1≤i≤φ19课堂小结1、费马小定理

设m为素数，a为任意整数，且（a，m）2、欧拉定理

设m为正整数，ɑ为任意整数，且（ɑ，m

）=1，则其中(m)

表示1，2，…，m中与m互素的正整数的个数.《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)课堂小结1、费马小定理设m为素数，a为任意整数，且（a，20针对性练习一、设a，b，c，m是正整数，m>1，(b,m)=1，并且b

a

1(modm)，b

c

1(modm)，记d=(a,c)，则bd

1(modm).解利用辗转相除法可以求出整数x，y，使得ax

cy=d，显然xy<0.若

x>0，y<0，由式(4)知

1

b

ax=b

dbcy=b

d(b

c)y

b

d(modm)。若

x<0，y>0，由式(4)知

1

b

cy=b

dbax=b

d(ba)x

b

d(modm)。《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)针对性练习一、设a，b，c，m是正整数，m>1，21

二、设p是素数，pbn1，nN，则下面的两个结论中至少有一个成立：(ⅰ)pbd1对于n的某个因数d<n成立；(ⅱ)p1(modn).p>2，则(ⅱ)中的modn可以改为mod2n.解记d=(n,p

1)，由bn1，bp11(modp)，及题一，有bd1(modp).《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)二、设p是素数，pbn1，nN，则下面的两个结论22

若d<n，则结论(ⅰ)得证.

若d=n，则np1，即p1(modn)，这就是结论(ⅱ).

p>2，则p1(mod2).由此及结论(ⅱ)，并利用同余的基本性质，得到p1(mod2n).

这是一种解题方法好好掌握吆.《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)若d<n，则结论(ⅰ)得证.23解由题二知

若p2351

则p是251=31或271=127的素因数

或者p1(mod70)

由于31和127是素数

并且2351=31*127*8727391

所以，2351的另外的素因数p只可能在数列三、将2351=34359738367分解因数.《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)解由题二知2471，211，281，

(5)中

经检验，得到8727391=71*122921.显然，122921的素因数在31，127或者数列(5)中说明，122921不能被31和127整除，也不能被数列(5)中的不超过的数整除，所以122921是素数于是

2351=31*127*71*122921.《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)71，211，281，(5)中25课堂练习1、313159被7除的余数（）.6(mod7)

2、132005被17除的余数（）.13(mod17)3、17x≡1（mod5），则x=（）.A.5B.6C.4D.7C4、5x≡1（mod6），则x=（）.A.5B.6C.4D.2D《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)课堂练习1、313159被7除的余数（265、设p，q是两个不同的素数，证明：pq

1

qp1

1(modpq).由费马定理：

qp

1

1(modp)，

pq1

1(modq)

pq1

qp1

1(modp)

pq1

qp1

1(modq)

故pq1

qp1

1(modpq).证明：《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)5、设p，q是两个不同的素数，证明：由费马定理：27

612

1=(631)(631)(661)=5*43*7*31*46657

对于46657，它的素因数必为12k1型，经检验的46657=13*37*97

故6121=5*7*13*31*37*43*97.6、将612

1分解成素因数之积.

解：《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)6121=(631)(631)(28证明：因561=3*11*17，对于一切整数a，(a,561)=1，有(a,3)=1，(a,11)=1，(a,17)=1，由费马定理可得a560=(a2)2801(mod3)，a560=(a10)561(mod11)，a560=(a16)351(mod17)，故a5601(mod561).7、证明：对于任意的整数a，(a,561)=1，都有a560

1(mod561)，但561是合数.

《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)证明：因561=3*11*17，对于一切整数a，(a,29再见《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)再见《费马小定理和欧拉定理》完整版人教版1-精品课件ppt30知识回顾剩余类定理

若a,b,c为任意3个整数，m为正整数，且(m,c)=1,则当ac≡bc(modm)时，有a≡b(modm)

如果a,b,c,d是四个整数，且a≡b(modm),c≡d(mod

m),则有ac≡bd(modm).

同余定理知识回顾剩余类定理若a,b,c为任意3个整数，m为正31导入新课

上一讲我们讲了剩余类，剩余环并知道了它的运算法则.剩余类乘法：[a][b]=[ɑb]在整数集模6的剩余环中[2][4]=[8]=[2][8][9]=[72]=[0][2][4][9]=[72]=[0]导入新课上一讲我们讲了剩余类，剩余环并知道了32当n为素数时，模n的剩余类环中无零因子.·[0][1][2][3][4][0][1][2][3][4]由以前学的知识在填写模5剩余环.[0][0][0][0][0][0][0][0][0][1][2][3][4][2][3][4][4][1][3][1][3][4][2][2][1]当n为素数时，模n的剩余类环中无零因子.·[0][1][2]33模7剩余环[07]=

.[17]=

.[27]=

.[37]=

.[47]=

.[57]=

.[67]=

.[05]=

.[15]=

.[25]=

.[35]=

.[45]=

.[03]=

.[13]=

.[23]=

.模5剩余环模3剩余环[6][5][4][3][2][0][1][4][3][2][0][1][2][0][1]对合数上述规律是否依然成立？找规律观察一模7剩余环[07]=34第三节费马小定理和欧拉定理第二讲同余与同余方程第三节费马小定理和欧拉定理第二讲同余与同余方程35教学目标知识与能力1.理解费马小定理和欧拉定理的内容与证明过程.2.能够运用费马小定理和欧拉定理简化数论中的一些计算问题.教学目标知识与能力1.理解费马小定理和欧拉定36情感态度与价值观过程与方法1.通过举例对比总结费马小定理和欧拉定理的定义.2.由以前学过的知识，对费马小定理和欧拉定理进行证明.

认识费马小定理和欧拉定理的历史及地位和作用.情感态度与价值观过程与方法1.通过举例对比总37教学重难点1.欧拉函数的定义及性质.

费马小定理和欧拉定理的证明过程，以及灵活运用这两个定理简化数论中的一些计算.

重点难点2.欧拉定理、Fermat小定理，循环小数的判定条件.教学重难点1.欧拉函数的定义及性质.费马小定理和欧38科普知识

瑞士著名的数学家欧拉,是数学史上的最多的数学家,他毕生从事数学研究,他的论著几乎涉及18世纪所以的数学分支.比如数学中的欧拉公式,欧拉方程.欧拉常数,欧拉方法.欧拉猜想等.欧拉晚年不幸双目失明，失明后的17年，他还口述署了几本书和约400篇论．科普知识瑞士著名的数学家欧拉,是数学史上的最39费马生于法国南部

，贡献包括：与笛卡尔共同创立了解析几何；创造了作曲线切线的方法

.最有名的是费马大定理，即不可能有满足xn+yn=zn，n>2的正整数x，y，z，n存在.费马小定理是费马在1640年提出.科普知识费马生于法国南部，贡献包括：与笛卡尔共同创40

通过观察一，我们得到模7剩余环、模5剩余环、模3剩余环的规律，又由于3、5、7都是素数，我们猜想：

费马小定理设m为素数，ɑ为任意整数，通过观察一，我们得到模7剩余环、模5剩余环、模3剩余41实例例一、若a=3，m=7，则am-1≡1（modm）成立否.解：有以前的知识我们知道3×1≡3（mod7）3×2≡6（mod7）3×3≡2（mod7）3×4≡5（mod7）3×5≡1（mod7）3×6≡4（mod7）则：36×6！≡6！（mod7）.(1)又因为：(6!,5)=1(2)所以：36≡1（mod7）即：am-1≡1（modm）实例例一、若a=3，m=7，则am-1≡1（modm）成立否42分析在例一的解析中我们用到了以前学习的知识.(1)中用到了等式左边相乘等于等式右边相乘.(2)中用到了同余的性质“若ɑb≡ɑc（modn），且（ɑ，n）=1，则b≡c（modn）”.

例一的解析符合费马小定理，下面我们用通式对费马小定理给予证明.分析在例一的解析中我们用到了以前学习的知识.(1)中用到了43设An=a,2a,3a,4a……(p-1)a

假设An中有2项ma,na

被p除以后余数是相同得ma=na(modp)即a(m-n)=0(modp)因为a和p互质,所以m-n=0(modp)又因为m,n属于集合{1,2,3..p-1}且m不等于n

所以m-n不可能是p的倍数.推出和假设产生矛盾.证明设An=a,2a,3a,4a……(p-1)a44所以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*3*4…*(p-1)(modp)对两边进行化简,即可以得到a(p-1)=1(modp)所以An中任意2项被p除得到的余数都不同45巩固1、11x≡1（mod3），则x=（）.2、114≡1（modx），则x=（）.3、116≡x（mod7），则x=（）.4、x6≡1（mod7），1-10之内x可能为（）.521、2、3、4、5、6、8、9、101巩固1、11x≡1（mod3），则x=（）.46

我们看到在费马小定理中针对的是m为素数的情况，对于其它数能否找到类似的性质呢，这就是下面要讲的欧拉定理.拓展

欧拉定理

设m为正整数，ɑ为任意整数，且（ɑ，m）=1，则我们看到在费马小定理中针对的是m为素数的情况，对于其47(1)

令

则Zn=S.

①因为a

与n

互质，xi(1≤i≤φ(n))与n

互质，所以a*xi

与n

互质，所以a*ximodn∈Zn.

②若i

≠j

，那么xi≠xj，且由a,n互质可得a*ximodn≠a*xjmodn

（消去律）.证明：(1)令证明：48

对比等式的左右两端，因为xi(1≤i≤φ(n))与n

互质，所以aφ(n)≡1modn

（消去律）.

（2）《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)对比等式的左右两端，因为xi(1≤i≤φ49课堂小结1、费马小定理

设m为素数，a为任意整数，且（a，m）2、欧拉定理

设m为正整数，ɑ为任意整数，且（ɑ，m

）=1，则其中(m)

表示1，2，…，m中与m互素的正整数的个数.《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)课堂小结1、费马小定理设m为素数，a为任意整数，且（a，50针对性练习一、设a，b，c，m是正整数，m>1，(b,m)=1，并且b

a

1(modm)，b

c

1(modm)，记d=(a,c)，则bd

1(modm).解利用辗转相除法可以求出整数x，y，使得ax

cy=d，显然xy<0.若

x>0，y<0，由式(4)知

1

b

ax=b

dbcy=b

d(b

c)y

b

d(modm)。若

x<0，y>0，由式(4)知

1

b

cy=b

dbax=b

d(ba)x

b

d(modm)。《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)针对性练习一、设a，b，c，m是正整数，m>1，51

二、设p是素数，pbn1，nN，则下面的两个结论中至少有一个成立：(ⅰ)pbd1对于n的某个因数d<n成立；(ⅱ)p1(modn).p>2，则(ⅱ)中的modn可以改为mod2n.解记d=(n,p

1)，由bn1，bp11(modp)，及题一，有bd1(modp).《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)二、设p是素数，pbn1，nN，则下面的两个结论52

若d<n，则结论(ⅰ)得证.

若d=n，则np1，即p1(modn)，这就是结论(ⅱ).

p>2，则p1(mod2).由此及结论(ⅱ)，并利用同余的基本性质，得到p1(mod2n).

这是一种解题方法好好掌握吆.《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)若d<n，则结论(ⅰ)得证.53解由题二知

若p2351

则p是251=31或271=127的素因数

或者p1(mod70)

由于31和127是素数

并且2351=31*127*8727391

所以，2351的另外的素因数p只可能在数列三、将2351=34359738367分解因数.《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)解由题二知5471，211，281，

(5)中

经检验，得到8727391=71*122921.显然，122921的素因数在31，127或者数列(5)中说明，122921不能被31和127整除，也不能被数列(5)中的不超过的数整除，所以122921是素数于是

2351=31*127*71*122921.《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)71，211，281，(5)中55课堂练习1、313159被7除的余数（）.6(mod7)

2、132005被17除的余数（）.13(mod17)3、17x≡1（mod5），则x=（）.A.5B.6C.4D.