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

初中数学兴趣班系列讲座数论部分 唐一良数学工作室第9讲 费尔马小定理一、基础知识：法国数学家费尔马在1640年提出了一个有关整数幂余数的定理，在解决许多关于某个整数幂除以某个整数的余数问题时非常方便有用，在介绍这个定理之前，我们先来看一些具体的同余式，请同学们注意观察，发现这些同余式符合什么规律31（mod 2），51（mod 2），71（mod 2）221（mod 3），421（mod 3），521（mod 3）241（mod 5），341（mod 5），441（mod 5）26（23）21（mod 7），36（33）21（mod 7），46（43）21（mod 7）这些同余式都符合同一个规律，这个规律就是费尔马小定理费尔马小定理：如果p是质数，（a，p）=1，那么ap11（mod p）与费马小定理相关的有一个中国猜想，这个猜想是中国数学家提出来的，其内容为：当且仅当2p-11(mod p)，p是一个质数。 假如p是一个质数的话，则2p-11(mod p)成立（这是费马小定理的一个特殊情况）是对的。但反过来，假如2p-11(mod p)成立那么p是一个质数是不成立的（比如341符合上述条件但不是一个质数）。 如上所述，中国猜测只有一半是正确的，符合中国猜测但不是质数的数被称为“伪质数”。 对于中国猜测稍作改动，即得到判断一个数是否为质数的一个方法：如果对于任意满足1 b 1,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,11，b是一个整数且(m,b)=1。如果a1,a2,a3,a4,am是模m的一个完全剩余系，则ba1,ba2,ba3,ba4,bam也构成模m的一个完全剩余系。证明：若存在2个整数bai和baj同余即baibaj (mod m)，根据引理1则有aiaj (mod m)。根据完全剩余系的定义可知这是不可能的，因此不存在2个整数bai和baj同余。由引理2可知ba1,ba2,ba3,ba4,bam构成模m的一个完全剩余系。引理4如果a,b,c,d是四个整数，且ab(mod m),cd(mod m),则有acbd(mod m)证明：由题设得acbc(mod m),bcbd(mod m)，由模运算的传递性可得acbc(mod m)（二）证明过程：构造素数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)，显然WW(mod p)。令Y=a*2a*3a*4a*(p-1)a,因为a,2a,3a,4a,(p-1)a是p的完全剩余系，由引理2以及引理4可得a*2a*3a*(p-1)a1*2*3*(p-1)(mod p)即W*ap-1W(modp)。易知(W,p)=1，由引理1可知ap-11(modp） 二、典型例题：例1 设为正整数.证明：的充要条件是.证明 若 ，则 |，于是，由Fermat小定理，知 从而，由 ，知 ，故 反过来，若 则 |，并且 ，即 ，利用小定理知 故 命题获证。说明 涉及指数的同余式经常需要用到小定理，因为由小定理得出的结论中，同余式的一边是，这带来很大的方便.例2 由小定理知，对任意奇质数，都有问：是否存在合数，使得成立？解 这样的合数存在，而且有无穷多个.其中最小的满足条件的合数（它是从两个不同奇质数作乘积去试算出来的）.事实上，由于 故 所以 故341符合要求. 进一步，设是一个符合要求的奇合数，则是一个奇合数（这一点利用因式分解可知）。再设为正奇数，则 因此也是一个符合要求的数.依此类推（结合符合要求），可知有无穷多个满足条件的合数.说明 满足题中的合数称为“伪质数”，如果对任意都有成立，那么合数称为“绝对伪质数”.请读者寻找“绝对伪质数”.例3 设为质数.证明：存在无穷多个正整数，使得.证明 如果，那么取为偶数，就有，命题成立.设，则由Fermat小定理知 因此，对任意正整数，都有 所以，只需证明存在无穷多个正整数，使得 （这样，令就有.而这只需这样的当然有无穷多个.所以，命题成立.说明 用Fermat小定理处理数论中的一些存在性问题有时非常方便、简洁.例4 设为整数，是的奇质因子，证明：证明 由于为奇质数，若则，可设，此时，由得 而由小定理，应有 结合上式将导出.矛盾. 所以， 说明 利用此题的结论，我们可以证明：存在无穷多个模余的正整数为质数. 事实上，若只有有限个质数模余，设它们是.考虑数的质因子即可导出矛盾.例5 求所有的质数，使得是一个完全平方数.解 设是一个满足条件的质数，则显然是一个奇质数.由小定理知 ，而 故 或由于 所以，与中恰有一个成立. 若，则由条件及可知存在正整数，使得 ，此时 所以，与都是的冥次，而为奇数，故与是两个相继的偶数，所以，只能是 故 ，此时 若，则同上知存在正整数，使得 当时，导致 矛盾，故 另一方面，当和时，分别为和，都是完全平方数.综上可知或.例6求14589+32002除以13的余数 解：因13是质数，且（145，13）=1，（3，13）=1 由费尔马小定理得：145121（mod 89），312（mod 89）14589（14512）714551455（mod 13）32002（312）166310310（mod 13）又1452（mod 13），331（mod 13）1455256（mod 13），310（33）333（mod 13）所以，14589+320026+39（mod 13），即14589+32002除以13的余数是9例7设p是质数，且p2求证：1p+2p+3p+（p1）p0（mod p）证明：由于p是质数且p2，所以对任意正整数np，都有（n，p）=1，根据费尔马小定理得，np11（mod p），于是npn（mod p）（n=1，2，3，p1）因此，1p+2 p+3 p+（p1）p1+2+3+（p1）（mod p）由于p是不等于2的质数，所以是整数故0（mod p），所以1p+2 p+（p1）p0（mod p）说明：费尔马小定理也可以写成另外一种形式：如果p是质数，对任意正整数a，都有apa（mod p），这是因为当p | a时，（p，a）=1，有ap11（mod p）故a pa（mod p）；当p | a时，显然有p | apa，即apa（mod p）费尔马小定理的逆定理不成立，也就是说，当ap11（mod p）时，p不一定是质数，例如531（mod 4），且（5，4）=1，但4不是质数例8求证：对任意整数a，b，ab(a4b4)都能被30整除分析：因为30=235，所以只需证明2 | ab(a4b4)，3 | ab(a4b4)，5 | ab(a4b4)，因为2，3，5都是质数，所以可以考虑用费尔马小定理证明：因为30=235，所以只需证明2，3，5都能整除ab(a4b4)即可，因2是质数，根据费尔马小定理得，a2a（mod 2），b2b（mod 2），所以a4（a2）2a2a（mod 2），b4（b2）2b2b（mod 2）ab(a4b4)ab（ab）a2bab2abab0（mod 2），即2 | ab(a4b4)又因为3也是质数，根据费尔马小定理得a3a（mod 3），b3b（mod 3）ab(a4b4)ab(a2b2)(mod 3)a3bab3(mod 3)abab（mod 3）0（mod 3），即3 | ab(a4b4)例9证明：对任意自然数n1，2n1都不能被n整除证明：若n为偶数，2n1必是奇数，则n | 2n1若n为奇数，且n1，假设n | 2n1设p为n的最小质因数，则2 n1（mod p），再设r是满足2 x1（mod p）的最小正整数，即2 r1（mod p），若r | x，可设x= kr+q，0qr，那么2 x2 k r+q（2 r）k2 q2q1（mod p）这与r的最小性矛盾，因此r | x，又因2 n1（mod p），所以r | n根据费尔马小定理得2p11（mod p），因此r | p1由r | n，r | p1知r是n的小于p的正约数，故r = 1，得p | 21，即p | 1，矛盾，假设不成立，即n | 2 n1，综上所述，对任意自然数n1，2n1都不能被n整除三、模拟训练：1.求出258000除以7的余数是多少。解：由于25与7互质，由费马小定理可知对模7而言，2561（mod 7）所以2580002561333+2（256）1333252422（mod 7）故余数为22.假设p为任意一个大于5的质数，试证：p必可整除np证明：由于p和10互质且9np10p-1-1,由费马小定理可知对模p而言，10p-11（mod p）因此，p一定能整除9np，又由于p和9互质，因此p一定能整除np3.假设p3k+2是一个质数，试证：如果p可整除a2+ab+b2(a和b都是整数)，那么a和b必定都是p的倍数。证明：由p可整除a2+ab+b2，p必定也能整除(a-b)(a2+ab+b2)a3-b3，因此a3b3（mod p）左右两边同时取k次方，得a3kb3k（mod p） (1)假设p不能整除a，那么p必定也不能整除b：由费马小定理可知对模p而言，ap-1bp-11（mod p）将p3k+2代入上式得：a3k+1b3k+11（mod p） (2)综合（1）（2）可知 ab1（mod p）因此a2+ab+b2a2+a2+a23a2（mod p）所以3a2是p的倍数，又3和p互质，可知a一定是p的倍数，这与假设p不能整除a矛盾，因此a和b必定都是p的倍数。四、【延伸阅读】（1）形如4k+1的质数个数有无数个。假设n是任意一个大于1的正整数：n!显然为偶数，因此(n!)2+1为奇数，而(n!)2+1的每个质因子都可表示为4k+1或4k-1的形式。假设p4k-1是(n!)2+1的一个质因子（可知p和n!互质），由于(n!)2 -1（mod p）将左右两边同时取次方，得(n!)p-1（mod p）由于2k-1为奇数，因此(n!)p-1 (-1)（mod p）但这与费马小定理矛盾，因此根据费马小定理，由于p和n!互质，(n!)p-1必定会和1对模p同余。 由此我们推知(n!)2+1不可能有形如4k-1的质因子，也就是(n!)2+1只有形如4k+1的质因子。又由于(n!)2+1的每个质因子显然都大于n，因此我们就证明了：不管n是多少，一定有比n大而且形如4k+1的质数存在，这就说明了等差数列1,5,9,13，中包含无穷多个质数。（2）费马小定理的逆定理当p为质数，由费马小定理我们知道2p-2必定是p的倍数（即前面的讨论中当a2的情形）；反过来成不成立呢？也就是说，如果有某个正整数n可以整除2n-2，我们能不能断定n一定是质数呢？如果可以的话，这将是个不错的判断任意整数n是否为质数的方法；历史上确实曾经有一段时期数学家们猜测这个方法可行，不过法国数学家Pierre Sarrus于1819年指出n341是一个反例：341是11与13的积，因此不是质数，但是由2341-22(210)34-1342(210-1)()2(1023)()2(3)(341)()可知341能整除2341-2.对任意正整数a，如果有某个大于1的正整数n本身不是质数却能整除an-a，我们称n对底数a而言是一个伪质数（英文常称作a-pseudoprime），因此对底数2而言，341是一个伪质数（即341是一个2-pseudoprime）。几个衍生出来的问题是：341是唯一的2-pseudoprime吗？除了奇数的伪质数外，是否还存在着偶伪质数？对任意正整数a，a-pseudoprime的个数是有限还是无限？对底数2而言，如果n是一个奇伪质数，我们不难证明2n-1将是另一个更大的奇伪质数；既然我们已知奇伪质数341的存在，对底数2来说奇伪质数的个数因此是无穷的，寻找偶伪质数（对底数2而言）的工作比寻找奇伪质数要困难许多，其中最小的数直到1950年才由美国数学家D.H.Lehmer找到，其值为1610382731103.由于2161038-22（2161037-1）要说明161038可以整除2161038-2，我们只要说明73和1103（皆为质数）都能整除2161037-1即可。由于161037可经质因数分解为3229617，因此2161037-12（29）29617-129617（29-1）（）（511）（）7（73）（）可知73能整除2161037-1。又由于2161037-12（229）9617-19617=（229-1）（）1103（486737）（）因此1103的确也能整除2161037-1，数学家N.G.W.H.Beeger于1951年还证明了对底数2而言，偶伪质数的个数也是无穷的。 数学上还能证明：对任意正整数a，以a为底数的伪质数的个数都是无穷的。（3）需要洗几次牌？考虑以下动作：将一副扑克牌（52张）由中间分成各含26张牌的两小迭，然后洗牌使得这两迭牌一张一张交错，重新组合成52张牌，下图显示了洗牌前后位置的变化：我们称上述动作为一次洗牌，请问：经过洗牌几次后可使得每张牌都回到它最原始的位置？由上图洗牌前后的位置变化，我们看到原来在位置编号1,2,3，26的牌经过一次洗牌后被放到编号为2,4,6，52的位置，而原来编号为27,28,29，52的牌则被放到了编号1,3,5,，51的位置，因此如果某