费马小定理及应用

11费马小定理及应用知识定位，卜 费马小定理是初中数学竞赛数论中经常出现的一种。要熟练掌握费马小定理是数论中的一个定理，数学表达形式和应用。本节我们通过一些实例的求解，旨在介绍数学竞赛中不定方程相关问题的常见题型及其求解方法本讲将通过例题来说明这些方法的运用。知识梳理*/- 1、欧拉函数：巾(m)是1,2,…，m中与m互质的个数，称为欧拉函数①欧拉函数值的计算公式：若m=pa1pa2…p%则"(m)=m(1—1)。一?)…。一；)12n p1 p2 pn111例如，30=2-3-5,则叭30)=30(1—-)(1--)(1-?=8.乙 J J②若p为素数，则U5(P)=P-1,5(Pk)=Pk-1(P-1),若p为合数，贝U①(p)<p-2,1③不超过n且与n互质的所有正整数的和为5n5(n)；④若(a,b)=1n5(ab)=5(a)5(b),若a|b=5(a)|5(b)n⑤设d为n的正约数，则不大于n且与n有最大公因数d的正整数个数为5(-)，d同时E5(d)=^5。)=n；dn dn2、欧拉定理:若(a,m)=1,则a小(m)三1(modm).证明：设r1,r2,…，.⑻是模m的简化剩余系，又,.，(&,m)=1,.,.a・r1,a・r2,…，&・.(此是模m的简化剩余系，/.a•r1Xa・r2X…Xa・三r1Xr2X…Xrgmjmodm),又■(ri・r2•…•m)=1，/.axm)三1(modm).应用：设(a,m)=1,c是使得ac三1(modm)的最小正整数，则c|巾(m).补充：设m>1是一个固定的整数，a是与m互质的整数，则存在整数k(IWkWm),使ak三1(modm),我们称具有这一性质的最小正整数(仍记为k)称为a模m的阶，由a模m的阶的定义，可得如下性质：(1)设(a,m)=1,k是a模m的阶，u,v是任意整数，则au三av(modm)的充要条件是u三v(modk),特别地，au三1(modm)的充要条件是k|u证明：充分性显然.必要性：设u>v,l=u-v,由au三av(modm)及(a,m)=1知ai三1(modm).

用带余除法，l=kq+r,0<r<k,故akq-ar三1(modm),，ar三1(modm),由k的定义知，必须r=0，所以u三v(modk).(2)设(a,m)=1,k是a模m的阶，则数列a,a%…，期ak+i,…是模m的周期数列，最小正周期为k,而k个数a,a%…，ak模m互不同余.(3)设(a,m)=1,k是a模m的阶，则k|巾(m),特别地，若m是素数P,则a模P的阶整除p—1.(4)设(a,p)=1,则d0是a对于模P的阶oad0三1(modp),且1,a,…，az对模p两两不同余.特别地，d°="(p)o1,a,…，a")-i构成模p的一个简化剩余系.定理：若l为a对模m的阶，s为某一正整数，满足as三1(modm),则s必为l的倍数.3、费尔马小定理若p是素数，则ap三a(modp)若另上条件(a,p)=1,则ap-i三1(modp)4、证明费马小定理的预备定理定义1：设a、b和m是整数，其中m>0,如果有m|(a一b)，则有a三b(modm)。在证明费马小定理之前,我们先给出几个引理引理1(剩余系定理2)若a,b,c为3个任意整数，m为正整数，若有ac三bc(modm)和(c,m)=1,则有a三b(modm)成立。证明：由条件可知ac-bc=0(modn)，化简有(a一b)c=0(modm)又因为(c,m)=1所以有a一b三0(modm),即有a三b(modm)£(n^Xc，-k£(n^Xc，-kyk，其中()=

kkn!k!(n一k)!k=0证明：根据二项式的展开定理,我们有：+Cn-1X1yn-1+CnX0yn

nn(x+y)n=+Cn-1X1yn-1+CnX0yn

nn=X=Xn+C1Xn-1y+

n+Cn-1Xyn-1+ynn由组合公式可得：£n(n)由组合公式可得：£n(n)Xn-k

kyk,其中kk=0n!k!(n一k)!引理3(多项式定理)如果冷k2,k3,……冷和n均是正整数，且有nN1和Vk2+k3+……+n，则有(x+x+ + x)n=乙Y xk1xk2…xkm1 2 m k1,k2,k3, km1 2 mk1+k2+k3+…+km=n其中(n!k1，k2，…kmk!k!•••k!12m(1)初等方法证明：对任意的非负整数m及素数p，恒有【2】(m+1)p=mp+C1mp+1+ +Cp-1m+1三mp+1(modp)pp即有(m+1)p-mp三1(modp)令m=0,1,2,3,……,a-1得p-0p三1(modp)p-1p三1(modp)p-2p三1(modp)(a-1)p-(a-2)p三1(modp)ap-(a-1)p三1(modp)上面各式分别相加得ap三a(modp)(2)二项式的展开法证明：设集合s={aap三a(modp)}，其中p是质数，aeN，因为0p=0，所以对任意的p有0p三0(modp)则0es现假设kes,则kP三p(modp)，我们要想得到k+1es,(k+1)p三(k+1)(modp)，通过二项式定理有:(k+1)p=kp+1p+£^p\p-j三k+1(modp)

jj=1如果(a,p)=1，则化简ap三a(modp)有ap-1三1(modp)如果a是负数，则对任意的r恒有a三r(modp)成立，其中0<r<p-1.从而有ap三rp三r三a(modp).4、威尔逊定理：P为质数O(p-1)!=-1(modp)证明：充分性：若P为质数，当P=2,3时成立，当p>3时，令x£{1,2,3,…，p-1},贝U(%,p)=1,在％,2%，…,(p-1)%中，必然有一个数除以p余1,这是因为%,2%，…，(p—1)%则好是p的一个剩余系去0.从而对V%€{1,2，…p一1},3y€{1,2，…,p一1}，使得%y三1(modp)；若%y三%y(modp),(%,p)=1,则%(y一y)三0(modp),p1(y一y)这不可能。1 2 12 12故对于不同的y,y€{1,2，…,p-1},有%y丰%y(modp).即对于不同的%对应于不12 1 2同的y,即1,2，…，p-1中数可两两配对，其积除以p余1,然后有%，使%2三1(modp),即与它自己配对，这时%2-1三0(modp),(%+1)(%-1)三0(modp),%=p-1或％=1.除%=1,p-1外，别的数可两两配对，积除以p余1.故(p-1)!三(p-1>1三-1(modp).必要性：若(p-1)!三一1(modP),假设P不是质数，则P有真约数d>1,故(p—1)!三一1(modd),另一方面，d<p,故d|(p—1)!,从而(p—1)!三0(modd),矛盾！••.P为质数.5、算术基本定理任何一个大于1的整数都可以分解成质数的乘积.如果不考虑这些质因子的次序,则这种分解法是唯一的.即对任一整数n>1,有n=pa1P：2…P：k,其中P1<P尸…<Pk均为素数，a1、a2、…、ak都是正整数.①正整数d是n的约数od=p%pB2…PT,(0WBWa,i=1,2,…，k)12k ii②由乘法原理可得：n的正约数的个数为r(n)=(a1+1)(a2+1)…(ak+1)③n的正约数的和为S(n)=(1+p1H HpaJd+p2H bpa2)…(1+PkH bp：J④n的正约数的积为T(n)=n2"n)⑤n为平方数的充要条件是：r(n)为奇数. _(1)判断质数的方法：设n是大于2的整数，如果不大于的质数都不是n的因子，则n是质数.(2)n!的标准分解：设P是不大于n的质数，则n!中含质数P的最高次幂为：nnn n 、P(n!)=[—]+[——]+[——]+…+[——](pm<n<pm+1).从而可以写出n!的标准分解式.Pp2p3 pm例题精讲【试题来源】【题目】证明：当质数p三7时，240|p4-1【答案】如下解析【解析】证明：•••PN—1=(P—1)(P+1)(P"2+1)1°大于7的质数必是奇数，・・.2|P-2+1；2°(P—1)(P+1)是连续偶数，・•・8|(P-1)(P+1)；(整数的性质一一两个连续偶数中,其中一个是4的倍数.)3°若P三±1(mod5)则5|(P—1)(P+1)若P三±2(mod5)则5|P"2+1；・•・5|(P—1)(P+1)(P"2+1)4°P是大于7的质数必是奇数，则P三±1(mod3).♦.3|(P—1)(P+1)p=7时，p-4-1=2400.综上所述：240P4—1【知识点】费马小定理及应用【适用场合】当堂例题【难度系数】4【试题来源】【题目】求20032005被17除所得的余数.【答案】14【解析】解：20032005=(17X114+14)2005三142005(mod17),因为(17,14)=1,所以由费马小定理得1416三1(mod17),故20032005三142005三1416x125+5三145三（一3）5三（一3）（一3）三（一4）（-3）=12（mod17）,所以20032005被17除所得的余数是14.【知识点】费马小定理及应用【适用场合】当堂练习【难度系数】3【试题来源】【题目】已知a为正整数，a三2,且(a,10)=1,求a20的末两位数字【答案】01【解析】 解：•・•(&,10)=1,・•.a为奇数，；.a20=a。(25)三1(mod25),又,「&2三1(mod4)na20三1(mod4),又,二(25,4)=1,/.a20=l(mod100),••.a2。的末两位数字01.【知识点】费马小定理及应用【适用场合】当堂例题【难度系数】3【试题来源】【题目】证明：方程12+5=y3无整数解.【答案】如下解析【解析】 证明：若y是偶数，则8|y3,X2三3(mod8)不可能.令x=2s,y=2t+1得2s2+2=4t3+612+3t,知t是偶数，令t=2j,代入得52+1=(16上2+12上+3)由(16j2+12j+3)三3(mod4)知存在4k+3型的奇素数P，使得p|(16j2+12j+3),从而p|S2+1,p=1 p-1即S2三一1(modp),有(s,p)=1,(s2)2三(-1)2(modp),于是sp-1三一1(modp)与费尔马小定理矛盾.【知识点】费马小定理及应用【适用场合】当堂练习题【难度系数】4【试题来源】【题目】试证：对于每一个素数p,总存在无穷多个正整数小使得p|2n-n..【答案】如下解析【解析】 证明：若p=2,则n为偶数时结论成立.若p>2,则(2,p)=1,由费尔马小定理2p-i三1(modp),故对于任意m,有2m(p-i)三1(modp)....2m(P-i)—m(p—1)三1+m(modp),令1+m三0(mod口)，即皿=卜口一1,则对于n=m(p—1)=(kp—1)(p—1)(k£N*),均有2n—n被p整除【知识点】费马小定理及应用【适用场合】当堂例题【难度系数】3【试题来源】【题目】设a,b为正整数，对任意的自然数n有an+nbn+n，则a=b.【答案】如下解析【解析】证明：假设a与b不相等.考虑n=1有a+1|b+1，则a<b.设p是一个大于b的素数，设n是满足条件的正整数:n三1(mod(p-1)),n三一a(modp),由孙子定理这样的n是存在的，如n=(a+l)(p—1)+1.由费马定理an=ak(p-i)+i三a(modp),所以an+n三0(modp),也即p\bn+n,再由费马定理bn+n三b-a(modp),所以p\b-a，矛盾.【知识点】费马小定理及应用【适用场合】当堂练习题【难度系数】4习题演练—【试题来源】【题目】设p是奇素数，证明：2p—1的任一素因了具有形式2px+1,x是正整数.【答案】如下解析【解析】证明：设q是2p—1的任一素因子，则qW2.设2模q的阶是k,则由2p三1(modq)知k|p,故k=1或p(因p是素数，这是能确定阶k的主要因素).显然kW1,否则21三1(modq),这不可能，因此k=p.由费马小定理2q-1三1(modq)推出kIq-1,即pIq-1.因p、q都是奇数，故q—1=2px(x是个正整数).【知识点】费马小定理及应用【适用场合】随堂