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

认识费马小定理和欧拉定理的历史及地位和作用.教学重难点1.欧拉函数的定义及性质.

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

重点难点2.欧拉定理、Fermat小定理，循环小数的判定条件.科普知识

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

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

.最有名的是费马大定理，即不可能有满足xn+yn=zn，n>2的正整数x，y，z，n存在.费马小定理是费马在1640年提出.科普知识

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

费马小定理设m为素数，ɑ为任意整数，实例例一、若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）分析在例一的解析中我们用到了以前学习的知识.(1)中用到了等式左边相乘等于等式右边相乘.(2)中用到了同余的性质“若ɑb≡ɑc（modn），且（ɑ，n）=1，则b≡c（modn）”.

例一的解析符合费马小定理，下面我们用通式对费马小定理给予证明.设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中任意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)巩固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

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

欧拉定理

设m为正整数，ɑ为任意整数，且（ɑ，m）=1，则(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

（消去律）.证明：

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

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

（消去律）.

（2）《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)课堂小结1、费马小定理

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

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

）=1，则其中

(m)

表示1，2，…，m中与m互素的正整数的个数.《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)针对性练习一、设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

db

cy=b

d(b

c)

y

b

d(modm)。若

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

1

b

cy=b

db

ax=b

d(ba)

x

b

d(modm)。《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)

二、设p是素数，p

bn

1，n

N，则下面的两个结论中至少有一个成立：(ⅰ)p

bd

1对于n的某个因数d<n成立；(ⅱ)p

1(modn).p>2，则(ⅱ)中的modn可以改为mod2n.解记d=(n,p

1)，由bn

1，bp

1

1(modp)，及题一，有bd

1(modp).《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)

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

若d=n，则n

p

1，即p

1(modn)，这就是结论(ⅱ).

p>2，则p

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

1(mod2n).

这是一种解题方法好好掌握吆.《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)解由题二知

若p

235

1

则p是25

1=31或27

1=127的素因数

或者p

1(mod70)

由于31和127是素数

并且235

1=31*127*8727391

所以，235

1的另外的素因数p只可能在数列三、将235

1=34359738367分解因数.《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)71，211，281，

(5)中

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

235

1=31*127*71*122921.《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)课堂练习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(实用版)5、设p，q是两个不同的素数，证明：pq

1

qp

1

1(modpq).由费马定理：

qp

1

1(modp)，

pq

1

1(modq)

pq

1

qp

1

1(modp)

pq

1

qp

1

1(modq)

故pq

1

qp

1

1(modpq).证明：《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)《费马小定理和欧拉定理》完整版人教版1-精品课件ppt(实用版)

612

1=(63

1)(63

1)(66

1)=5*43*7*31*46657