《2021年初中数学竞赛讲座数论部分费马小定理.doc》由会员分享，可在线阅读，更多相关《2021年初中数学竞赛讲座数论部分费马小定理.doc（13页珍藏版）》请在金锄头文库上搜索。
1、第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是质数
2、，（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,a
3、m为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,
4、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-
5、1)a1*2*3*(p-1)(mod p)即W*ap-1W(modp)。易知(W,p)=1，由引理1可知ap-11(modp） 二、典型例题：例1 设为正整数.证明：充要条件是.证明 若 ，则 |，于是，由Fermat小定理，知 从而，由 ，知 ，故 反过来，若 则 |，并且 ，即 ，运用小定理知 故 命题获证。阐明 涉及指数同余式经常需要用到小定理，由于由小定理得出结论中，同余式一边是，这带来很大以便.例2 由小定理知，对任意奇质数，均有问：与否存在合数，使得成立？解 这样合数存在，并且有无穷各种.其中最小满足条件合数（它是从两个不同奇质数作乘积去试算出来）.事实上，由于 故 因此 故341
6、符合规定. 进一步，设是一种符合规定奇合数，则是一种奇合数（这一点运用因式分解可知）。再设为正奇数，则 因而也是一种符合规定数.依此类推（结合符合规定），可知有无穷各种满足条件合数.阐明 满足题中合数称为“伪质数”，如果对任意均有成立，那么合数称为“绝对伪质数”.请读者寻找“绝对伪质数”.例3 设为质数.证明：存在无穷各种正整数，使得.证明 如果，那么取为偶数，就有，命题成立.设，则由Fermat小定理知 因而，对任意正整数，均有 因此，只需证明存在无穷各种正整数，使得 （这样，令就有.而这只需这样固然有无穷各种.因此，命题成立.阐明 用Fermat小定理解决数论中某些存在性问题有时非常以便、
7、简洁.例4 设为整数，是奇质因子，证明：证明 由于为奇质数，若则，可设，此时，由得 而由小定理，应有 结合上式将导出.矛盾. 因此， 阐明 运用此题结论，咱们可以证明：存在无穷各种模余正整数为质数. 事实上，若只有有限个质数模余，设它们是.考虑数质因子即可导出矛盾.例5 求所有质数，使得是一种完全平方数.解 设是一种满足条件质数，则显然是一种奇质数.由小定理知 ，而 故 或由于 因此，与中恰有一种成立. 若，则由条件及可知存在正整数，使得 ，此时 因此，与都是冥次，而为奇数，故与是两个相继偶数，因此，只能是 故 ，此时 若，则同上知存在正整数，使得 当时，导致 矛盾，故 另一方面，当和时，分别
8、为和，都是完全平方数.综上可知或.例6求14589+3除以13余数 解：因13是质数，且（145，13）=1，（3，13）=1 由费尔马小定理得：145121（mod 89），312（mod 89）14589（14512）714551455（mod 13）3（312）166310310（mod 13）又1452（mod 13），331（mod 13）1455256（mod 13），310（33）333（mod 13）因此，14589+36+39（mod 13），即14589+3除以13余数是9例7设p是质数，且p2求证：1p+2p+3p+（p1）p0（mod p）证明：由于p是质数且p2，因此
9、对任意正整数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
10、 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
11、 | 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.求出
