《費馬小定理和歐拉定理》完整版 人教版1課件

知識回顧剩余類定理

若a,b,c為任意3個整數(shù)，m為正整數(shù)，且(m,c)=1,則當ac≡bc(modm)時，有a≡b(modm)

如果a,b,c,d是四個整數(shù)，且a≡b(modm),c≡d(mod

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

同余定理知識回顧剩余類定理若a,b,c為任意3個整數(shù)，m為正1導入新課

上一講我們講了剩余類，剩余環(huán)并知道了它的運算法則.剩余類乘法：[a][b]=[ɑb]在整數(shù)集模6的剩余環(huán)中[2][4]=[8]=[2][8][9]=[72]=[0][2][4][9]=[72]=[0]導入新課上一講我們講了剩余類，剩余環(huán)并知道了2當n為素數(shù)時，模n的剩余類環(huán)中無零因子.·[0][1][2][3][4][0][1][2][3][4]由以前學的知識在填寫模5剩余環(huán).[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為素數(shù)時，模n的剩余類環(huán)中無零因子.·[0][1][2]3模7剩余環(huán)[07]=

.[17]=

.[27]=

.[37]=

.[47]=

.[57]=

.[67]=

.[05]=

.[15]=

.[25]=

.[35]=

.[45]=

.[03]=

.[13]=

.[23]=

.模5剩余環(huán)模3剩余環(huán)[6][5][4][3][2][0][1][4][3][2][0][1][2][0][1]對合數(shù)上述規(guī)律是否依然成立？找規(guī)律觀察一模7剩余環(huán)[07]=4第三節(jié)費馬小定理和歐拉定理第二講同余與同余方程第三節(jié)費馬小定理和歐拉定理第二講同余與同余方程5教學目標知識與能力1.理解費馬小定理和歐拉定理的內(nèi)容與證明過程.2.能夠運用費馬小定理和歐拉定理簡化數(shù)論中的一些計算問題.教學目標知識與能力1.理解費馬小定理和歐拉定6情感態(tài)度與價值觀過程與方法1.通過舉例對比總結費馬小定理和歐拉定理的定義.2.由以前學過的知識，對費馬小定理和歐拉定理進行證明.

認識費馬小定理和歐拉定理的歷史及地位和作用.情感態(tài)度與價值觀過程與方法1.通過舉例對比總7教學重難點1.歐拉函數(shù)的定義及性質.

費馬小定理和歐拉定理的證明過程，以及靈活運用這兩個定理簡化數(shù)論中的一些計算.

重點難點2.歐拉定理、Fermat小定理，循環(huán)小數(shù)的判定條件.教學重難點1.歐拉函數(shù)的定義及性質.費馬小定理和歐8科普知識

瑞士著名的數(shù)學家歐拉,是數(shù)學史上的最多的數(shù)學家,他畢生從事數(shù)學研究,他的論著幾乎涉及18世紀所以的數(shù)學分支.比如數(shù)學中的歐拉公式,歐拉方程.歐拉常數(shù),歐拉方法.歐拉猜想等.歐拉晚年不幸雙目失明，失明后的17年，他還口述署了幾本書和約400篇論．科普知識瑞士著名的數(shù)學家歐拉,是數(shù)學史上的最9費馬生于法國南部

，貢獻包括：與笛卡爾共同創(chuàng)立了解析幾何；創(chuàng)造了作曲線切線的方法

.最有名的是費馬大定理，即不可能有滿足xn+yn=zn，n>2的正整數(shù)x，y，z，n存在.費馬小定理是費馬在1640年提出.科普知識費馬生于法國南部，貢獻包括：與笛卡爾共同創(chuàng)10

通過觀察一，我們得到模7剩余環(huán)、模5剩余環(huán)、模3剩余環(huán)的規(guī)律，又由于3、5、7都是素數(shù)，我們猜想：

費馬小定理設m為素數(shù)，ɑ為任意整數(shù)，通過觀察一，我們得到模7剩余環(huán)、模5剩余環(huán)、模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?。╩od7）.(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除以后余數(shù)是相同得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的倍數(shù).推出和假設產(chǎn)生矛盾.證明設An=a,2a,3a,4a……(p-1)a14所以An中任意2項被p除得到的余數(shù)都不同又因為對于任一個整數(shù)被p除以后的余數(shù)最多有p-1個,分別是1,2,3,….p-1而數(shù)列An中恰好有p-1個數(shù),所以數(shù)列中的數(shù)被p除以后的余數(shù)一定正好包含所有的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除得到的余數(shù)都不同15鞏固1、11x≡1（mod3），則x=（）.2、114≡1（modx），則x=（）.3、116≡x（mod7），則x=（）.4、x6≡1（mod7），1-10之內(nèi)x可能為（）.521、2、3、4、5、6、8、9、101鞏固1、11x≡1（mod3），則x=（）.16

我們看到在費馬小定理中針對的是m為素數(shù)的情況，對于其它數(shù)能否找到類似的性質呢，這就是下面要講的歐拉定理.拓展

歐拉定理

設m為正整數(shù)，ɑ為任意整數(shù)，且（ɑ，m）=1，則我們看到在費馬小定理中針對的是m為素數(shù)的情況，對于其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為素數(shù)，a為任意整數(shù)，且（a，m）2、歐拉定理

設m為正整數(shù)，ɑ為任意整數(shù)，且（ɑ，m

）=1，則其中(m)

表示1，2，…，m中與m互素的正整數(shù)的個數(shù).《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)課堂小結1、費馬小定理設m為素數(shù)，a為任意整數(shù)，且（a，20針對性練習一、設a，b，c，m是正整數(shù)，m>1，(b,m)=1，并且b

a

1(modm)，b

c

1(modm)，記d=(a,c)，則bd

1(modm).解利用輾轉相除法可以求出整數(shù)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)?！顿M馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)針對性練習一、設a，b，c，m是正整數(shù)，m>1，21

二、設p是素數(shù)，pbn1，nN，則下面的兩個結論中至少有一個成立：(ⅰ)pbd1對于n的某個因數(shù)d<n成立；(ⅱ)p1(modn).p>2，則(ⅱ)中的modn可以改為mod2n.解記d=(n,p

1)，由bn1，bp11(modp)，及題一，有bd1(modp).《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)二、設p是素數(shù)，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的素因數(shù)

或者p1(mod70)

由于31和127是素數(shù)

并且2351=31*127*8727391

所以，2351的另外的素因數(shù)p只可能在數(shù)列三、將2351=34359738367分解因數(shù).《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)解由題二知2471，211，281，

(5)中

經(jīng)檢驗，得到8727391=71*122921.顯然，122921的素因數(shù)在31，127或者數(shù)列(5)中說明，122921不能被31和127整除，也不能被數(shù)列(5)中的不超過的數(shù)整除，所以122921是素數(shù)于是

2351=31*127*71*122921.《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)71，211，281，(5)中25課堂練習1、313159被7除的余數(shù)（）.6(mod7)

2、132005被17除的余數(shù)（）.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除的余數(shù)（265、設p，q是兩個不同的素數(shù)，證明：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是兩個不同的素數(shù)，證明：由費馬定理：27

612

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

對于46657，它的素因數(shù)必為12k1型，經(jīng)檢驗的46657=13*37*97

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

1分解成素因數(shù)之積.

解：《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)6121=(631)(631)(28證明：因561=3*11*17，對于一切整數(shù)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、證明：對于任意的整數(shù)a，(a,561)=1，都有a560

1(mod561)，但561是合數(shù).

《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)證明：因561=3*11*17，對于一切整數(shù)a，(a,29再見《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)再見《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt30知識回顧剩余類定理

若a,b,c為任意3個整數(shù)，m為正整數(shù)，且(m,c)=1,則當ac≡bc(modm)時，有a≡b(modm)

如果a,b,c,d是四個整數(shù)，且a≡b(modm),c≡d(mod

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

同余定理知識回顧剩余類定理若a,b,c為任意3個整數(shù)，m為正31導入新課

上一講我們講了剩余類，剩余環(huán)并知道了它的運算法則.剩余類乘法：[a][b]=[ɑb]在整數(shù)集模6的剩余環(huán)中[2][4]=[8]=[2][8][9]=[72]=[0][2][4][9]=[72]=[0]導入新課上一講我們講了剩余類，剩余環(huán)并知道了32當n為素數(shù)時，模n的剩余類環(huán)中無零因子.·[0][1][2][3][4][0][1][2][3][4]由以前學的知識在填寫模5剩余環(huán).[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為素數(shù)時，模n的剩余類環(huán)中無零因子.·[0][1][2]33模7剩余環(huán)[07]=

.[17]=

.[27]=

.[37]=

.[47]=

.[57]=

.[67]=

.[05]=

.[15]=

.[25]=

.[35]=

.[45]=

.[03]=

.[13]=

.[23]=

.模5剩余環(huán)模3剩余環(huán)[6][5][4][3][2][0][1][4][3][2][0][1][2][0][1]對合數(shù)上述規(guī)律是否依然成立？找規(guī)律觀察一模7剩余環(huán)[07]=34第三節(jié)費馬小定理和歐拉定理第二講同余與同余方程第三節(jié)費馬小定理和歐拉定理第二講同余與同余方程35教學目標知識與能力1.理解費馬小定理和歐拉定理的內(nèi)容與證明過程.2.能夠運用費馬小定理和歐拉定理簡化數(shù)論中的一些計算問題.教學目標知識與能力1.理解費馬小定理和歐拉定36情感態(tài)度與價值觀過程與方法1.通過舉例對比總結費馬小定理和歐拉定理的定義.2.由以前學過的知識，對費馬小定理和歐拉定理進行證明.

認識費馬小定理和歐拉定理的歷史及地位和作用.情感態(tài)度與價值觀過程與方法1.通過舉例對比總37教學重難點1.歐拉函數(shù)的定義及性質.

費馬小定理和歐拉定理的證明過程，以及靈活運用這兩個定理簡化數(shù)論中的一些計算.

重點難點2.歐拉定理、Fermat小定理，循環(huán)小數(shù)的判定條件.教學重難點1.歐拉函數(shù)的定義及性質.費馬小定理和歐38科普知識

瑞士著名的數(shù)學家歐拉,是數(shù)學史上的最多的數(shù)學家,他畢生從事數(shù)學研究,他的論著幾乎涉及18世紀所以的數(shù)學分支.比如數(shù)學中的歐拉公式,歐拉方程.歐拉常數(shù),歐拉方法.歐拉猜想等.歐拉晚年不幸雙目失明，失明后的17年，他還口述署了幾本書和約400篇論．科普知識瑞士著名的數(shù)學家歐拉,是數(shù)學史上的最39費馬生于法國南部

，貢獻包括：與笛卡爾共同創(chuàng)立了解析幾何；創(chuàng)造了作曲線切線的方法

.最有名的是費馬大定理，即不可能有滿足xn+yn=zn，n>2的正整數(shù)x，y，z，n存在.費馬小定理是費馬在1640年提出.科普知識費馬生于法國南部，貢獻包括：與笛卡爾共同創(chuàng)40

通過觀察一，我們得到模7剩余環(huán)、模5剩余環(huán)、模3剩余環(huán)的規(guī)律，又由于3、5、7都是素數(shù)，我們猜想：

費馬小定理設m為素數(shù)，ɑ為任意整數(shù)，通過觀察一，我們得到模7剩余環(huán)、模5剩余環(huán)、模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?。╩od7）.(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除以后余數(shù)是相同得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的倍數(shù).推出和假設產(chǎn)生矛盾.證明設An=a,2a,3a,4a……(p-1)a44所以An中任意2項被p除得到的余數(shù)都不同又因為對于任一個整數(shù)被p除以后的余數(shù)最多有p-1個,分別是1,2,3,….p-1而數(shù)列An中恰好有p-1個數(shù),所以數(shù)列中的數(shù)被p除以后的余數(shù)一定正好包含所有的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除得到的余數(shù)都不同45鞏固1、11x≡1（mod3），則x=（）.2、114≡1（modx），則x=（）.3、116≡x（mod7），則x=（）.4、x6≡1（mod7），1-10之內(nèi)x可能為（）.521、2、3、4、5、6、8、9、101鞏固1、11x≡1（mod3），則x=（）.46

我們看到在費馬小定理中針對的是m為素數(shù)的情況，對于其它數(shù)能否找到類似的性質呢，這就是下面要講的歐拉定理.拓展

歐拉定理

設m為正整數(shù)，ɑ為任意整數(shù)，且（ɑ，m）=1，則我們看到在費馬小定理中針對的是m為素數(shù)的情況，對于其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為素數(shù)，a為任意整數(shù)，且（a，m）2、歐拉定理

設m為正整數(shù)，ɑ為任意整數(shù)，且（ɑ，m

）=1，則其中(m)

表示1，2，…，m中與m互素的正整數(shù)的個數(shù).《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)課堂小結1、費馬小定理設m為素數(shù)，a為任意整數(shù)，且（a，50針對性練習一、設a，b，c，m是正整數(shù)，m>1，(b,m)=1，并且b

a

1(modm)，b

c

1(modm)，記d=(a,c)，則bd

1(modm).解利用輾轉相除法可以求出整數(shù)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)?！顿M馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)針對性練習一、設a，b，c，m是正整數(shù)，m>1，51

二、設p是素數(shù)，pbn1，nN，則下面的兩個結論中至少有一個成立：(ⅰ)pbd1對于n的某個因數(shù)d<n成立；(ⅱ)p1(modn).p>2，則(ⅱ)中的modn可以改為mod2n.解記d=(n,p

1)，由bn1，bp11(modp)，及題一，有bd1(modp).《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)二、設p是素數(shù)，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的素因數(shù)

或者p1(mod70)

由于31和127是素數(shù)

并且2351=31*127*8727391

所以，2351的另外的素因數(shù)p只可能在數(shù)列三、將2351=34359738367分解因數(shù).《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)解由題二知5471，211，281，

(5)中

經(jīng)檢驗，得到8727391=71*122921.顯然，122921的素因數(shù)在31，127或者數(shù)列(5)中說明，122921不能被31和127整除，也不能被數(shù)列(5)中的不超過的數(shù)整除，所以122921是素數(shù)于是

2351=31*127*71*122921.《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)《費馬小定理和歐拉定理》完整版人教版1-精品課件ppt(實用版)71，211，281，(5)中55課堂練習1、313159被7除的余數(shù)（）.6(mod7)

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