初中数学竞赛讲座——数论部分9(费马小定理)

初中数学兴趣班系列讲座——数论部分唐一良数学工作室第1页共8页第9讲费尔马小定理一、基础知识：法国数学家费尔马在1640年提出了一个有关整数幂余数的定理，在解决许多关于某个整数幂除以某个整数的余数问题时非常方便有用，在介绍这个定理之前，我们先来看一些具体的同余式，请同学们注意观察，发现这些同余式符合什么规律．3≡1（mod2），5≡1（mod2），7≡1（mod2）…22≡1（mod3），42≡1（mod3），52≡1（mod3）…24≡1（mod5），34≡1（mod5），44≡1（mod5）…26≡（23）2≡1（mod7），36≡（33）2≡1（mod7），46≡（43）2≡1（mod7）…这些同余式都符合同一个规律，这个规律就是费尔马小定理．费尔马小定理：如果p是质数，（a，p）=1，那么ap－1≡1（modp）与费马小定理相关的有一个中国猜想，这个猜想是中国数学家提出来的，其内容为：当且仅当2p-1≡1(modp)，p是一个质数。假如p是一个质数的话，则2p-1≡1(modp)成立（这是费马小定理的一个特殊情况）是对的。但反过来，假如2p-1≡1(modp)成立那么p是一个质数是不成立的（比如341符合上述条件但不是一个质数）。如上所述，中国猜测只有一半是正确的，符合中国猜测但不是质数的数被称为“伪质数”。对于中国猜测稍作改动，即得到判断一个数是否为质数的一个方法：如果对于任意满足1bp的b下式都成立：bp-1≡1(modp)，则p必定是一个质数。实际上，没有必要测试所有的小于p的自然数，只要测试所有的小于p的质数就可以了。这个算法的缺点是它非常慢，运算率高；但是它很适合在计算机上面运行程序进行验算一个数是否是质数。（一）准备知识：引理1．若a,b,c为任意3个整数，m为正整数，且(m,c)=1,则当ac≡bc(modm)时，有a≡b(modm)证明：ac≡bc(modm)可得ac–bc≡0(modm)可得(a-b)c≡0(modm)因为(m,c)=1即m,c互质，c可以约去，a–b≡0(modm)可得a≡b(modm)引理2．若m为整数且m1,a1,a2,a3,a4,…am为m个整数，若在这m个数中任取2个整数对m不同余，则这m个整数对m构成完全剩余系。证明：构造m的完全剩余系（0,1,2,…m-1），所有的整数必然是这些整数中的1个对模m同余。取r1=0,r2=1,r3=2,r4=3,…ri=i-1,1i≤m。初中数学兴趣班系列讲座——数论部分唐一良数学工作室第2页共8页令(1)：a1≡r1(modm),a2≡r2(modm),…am≡rm(modm)(顺序可以不同),因为只有在这种情况下才能保证集合{a1,a2,a3,a4,…am}中的任意2个数不同余，否则必然有2个数同余。由式(1)自然得到集合{a1,a2,a3,a4,…am}对m构成完全剩余系。引理3．设m是一个整数，且m1，b是一个整数且(m,b)=1。如果a1,a2,a3,a4,…am是模m的一个完全剩余系，则ba1,ba2,ba3,ba4,…bam也构成模m的一个完全剩余系。证明：若存在2个整数bai和baj同余即bai≡baj(modm)，根据引理1则有ai≡aj(modm)。根据完全剩余系的定义可知这是不可能的，因此不存在2个整数bai和baj同余。由引理2可知ba1,ba2,ba3,ba4,…bam构成模m的一个完全剩余系。引理4．如果a,b,c,d是四个整数，且a≡b(modm),c≡d(modm),则有ac≡bd(modm)证明：由题设得ac≡bc(modm),bc≡bd(modm)，由模运算的传递性可得ac≡bc(modm)（二）证明过程：构造素数p的完全剩余系P={1,2,3,4…(p-1)}，因为(a,p)=1，由引理3可得A={a,2a,3a,4a,…(p-1)a}也是p的一个完全剩余系。令W=1*2*3*4…*(p-1)，显然W≡W(modp)。令Y=a*2a*3a*4a*…(p-1)a,因为{a,2a,3a,4a,…(p-1)a}是p的完全剩余系，由引理2以及引理4可得a*2a*3a*…(p-1)a≡1*2*3*…(p-1)(modp)即W*ap-1≡W(modp)。易知(W,p)=1，由引理1可知ap-1≡1(modp）二、典型例题：例1设n为正整数.证明：373nn的充要条件是1373nn.证明若337nn，则7|n，于是，由Fermat小定理，知),7(mod16n从而，由337nn，知33)3(7nnn，故.1373nn反过来，若,1373nn则7|n，并且337(31)nnn，即6373nnn，初中数学兴趣班系列讲座——数论部分唐一良数学工作室第3页共8页利用Fermat小定理知),7(mod16n故.373nn命题获证。说明涉及指数的同余式经常需要用到Fermat小定理，因为由Fermat小定理得出的结论中，同余式的一边是1，这带来很大的方便.例2由Fermat小定理知，对任意奇质数p，都有).(mod121pp问：是否存在合数n，使得)(mod121nn成立？解这样的合数n存在，而且有无穷多个.其中最小的满足条件的合数3111341n（它是从两个不同奇质数作乘积去试算出来的）.事实上，由于11210,3341023故),341(mod1210所以),341(mod11234340故341符合要求.进一步，设a是一个符合要求的奇合数，则12a是一个奇合数（这一点利用因式分解可知）。再设,121qaaq为正奇数，则1212)12(2112aa122aq1)2(2qa112q).12(mod0a因此12a也是一个符合要求的数.依此类推（结合341符合要求），可知有无穷多个满足条件的合数.说明满足题中的合数n称为“伪质数”，如果对任意1),(na都有)(mod11nan成立，那么合数n称为“绝对伪质数”.请读者寻找“绝对伪质数”.例3设p为质数.证明：存在无穷多个正整数n，使得npn2.证明如果2p，那么取n为偶数，就有npn2，命题成立.设2p，则由Fermat小定理知).(mod121pp因此，对任意正整数k，都有),(mod12)1(ppk所以，只需证明存在无穷多个正整数k，使得)(mod1)1(ppk（这样，令),1(pkn就有)2npn.而这只需),(mod1pk这样的k当然有无穷多个.所以，命题成立.说明用Fermat小定理处理数论中的一些存在性问题有时非常方便、简洁.初中数学兴趣班系列讲座——数论部分唐一良数学工作室第4页共8页例4设x为整数，p是12x的奇质因子，证明：).4(mod1p证明由于p为奇质数，若p≡／),4(mod1则)4(mod3p，可设34kp，此时，由),(mod12px得).(mod1)1()(12122241pxxxkkkp而由Fermat小定理，应有),(mod11pxp结合上式将导出2p.矛盾.所以，).4(mod1p说明利用此题的结论，我们可以证明：存在无穷多个模4余1的正整数为质数.事实上，若只有有限个质数模4余1，设它们是nppp,,,21.考虑数1)2(221nppp的质因子即可导出矛盾.例5求所有的质数p，使得pp121是一个完全平方数.解设p是一个满足条件的质数，则显然p是一个奇质数.由Fermat小定理知121pp，而),12)(12(1221211ppp故1221pp或.1221pp由于,1)2,12()12,12(212121ppp所以，1221pp与1221pp中恰有一个成立.若1221pp，则由条件及1)12,12(2121pp可知存在正整数x，使得22112xp，此时,2)1)(1(21pxx所以，1x与1x都是2的冥次，而x为奇数，故1x与1x是两个相继的偶数，所以，只能是,41,21xx故3x，此时.7p若1221pp，则同上知存在正整数x，使得初中数学兴趣班系列讲座——数论部分唐一良数学工作室第5页共8页,12221xp当3p时，导致),4(mod112212px矛盾，故.3p另一方面，当.3p和7时，pp121分别为1和9，都是完全平方数.综上可知3p或7.例6．求14589+32002除以13的余数．解：因13是质数，且（145，13）=1，（3，13）=1由费尔马小定理得：14512≡1（mod89），312≡（mod89）∴14589≡（14512）7·1455≡1455（mod13）32002≡（312）166·310≡310（mod13）又∵145≡2（mod13），33≡1（mod13）∴1455≡25≡6（mod13），310≡（33）33≡3（mod13）所以，14589+32002≡6+3≡9（mod13），即14589+32002除以13的余数是9．例7．设p是质数，且p≠2．求证：1p+2p+3p+…+（p－1）p≡0（modp）证明：由于p是质数且p≠2，所以对任意正整数n＜p，都有（n，p）=1，根据费尔马小定理得，np－1≡1（modp），于是np≡n（modp）（n=1，2，3，…，p－1）因此，1p+2p+3p+…+（p－1）p≡1+2+3+…+（p－1）（modp）≡)(mod2)1(ppp由于p是不等于2的质数，所以21p是整数．故2)1(pp≡0（modp），所以1p+2p+…+（p－1）p≡0（modp）说明：①费尔马小定理也可以写成另外一种形式：如果p是质数，对任意正整数a，都有ap≡a（modp），这是因为当p|a时，（p，a）=1，有ap－1≡1（modp）故ap≡a（modp）；当p|a时，显然有p|ap－a，即ap≡a（modp）．②费尔马小定理的逆定理不成立，也就是说，当ap－1≡1（modp）时，p不一定是质数，例如53≡1（mod4），且（5，4）=1，但4不是质数．例8．求证：对任意整数a，b，ab(a4－b4)都能被30整除．分析：因为30=2×3×5，所以只需证明2|ab(a4－b4)，3|ab(a4－b4)，5|ab(a4－b4)，因为2，3，5都是质数，所以可以考虑用费尔马小定理．证明：因为30=2×3×5，所以只需证明2，3，5都能整除ab(a4－b4)即可，因2是质数，根据费尔马小定理得，a2≡a（mod2），b2≡b（mod2），所以a4≡（a2）2≡a2≡a（mod2），b4≡（b2）2≡b2≡b（mod2）∴ab(a4－b4)≡ab（a－b）≡a2b－ab2≡ab－ab≡0（mod2），即2|ab(a4－b4)．又因为3也是质数，根据费尔马小定理得a3≡a（mod3），b3≡b（mod3）初中数学兴趣班系列讲座——数论部分唐一良数学工作室第6页共8页∴ab(a4－b4)≡ab(a2－b2)(mod3)≡a3b－ab3(mod3)≡ab－ab（mod3）≡0（mod3），即3|ab(a4－b4)．例9．证明：对任意自然数n＞1，2n－1都不能被n整除证明：若n为偶数，2n－1必是奇数，则n|2n－1若n为奇数，且n＞1，假设n|2n－1设p为n的最小质因数，则2n≡1（modp），再设r是满足2x≡1（modp）的最小正整数，即2r≡1（modp），若r|x，可设x=kr+q，0＜q＜r，那么2x≡2kr+q≡（2r）k·2q≡2q≡1（modp）这与r的最小性矛盾，因此r|x，又因2n≡1（modp），所以r|n．根据费尔马小定理得2p－1≡1（modp），因此r|p－1由r|n，r|p－1知r是n的小于p的正约数，故r=1，得p|2－1，即p|1，矛盾，假设不成立，即n|2n－1，综上所述，对任意自然数n＞1，2n－1都不能被n整除