第9讲费尔马小定理
一、基础知识：
法国数学家费尔马在1640年提出了一个有关整数幂余数的定理，在解决许多关于某个整数幂除以某个整数的余数问题时非常方便有用，在介绍这个定理之前，我们先来看一些具体的同余式，请同学们注意观察，发现这些同余式符合什么规律．
3≡1（mod 2），5≡1（mod 2），7≡1（mod 2）…
22≡1（mod 3），42≡1（mod 3），52≡1（mod 3）…
24≡1（mod 5），34≡1（mod 5），44≡1（mod 5）…
26≡（23）2≡1（mod 7），36≡（33）2≡1（mod 7），46≡（43）2≡1（mod 7）…
这些同余式都符合同一个规律，这个规律就是费尔马小定理．
费尔马小定理：如果p是质数，（a，p）=1，那么a p－1≡1（mod p）
与费马小定理相关的有一个中国猜想，这个猜想是中国数学家提出来的，其内容为：当且仅当2p-1≡1(mod p)，p是一个质数。
假如p是一个质数的话，则2p-1≡1(mod p)成立（这是费马小定理的一个特殊情况）是对的。但反过来，假如2p-1≡1(mod p)成立那么p是一个质数是不成立的（比如341符合上述条件但不是一个质数）。
如上所述，中国猜测只有一半是正确的，符合中国猜测但不是质数的数被称为“伪质数”。
对于中国猜测稍作改动，即得到判断一个数是否为质数的一个方法：
如果对于任意满足1 < b< p的b下式都成立：b p-1≡1(mod p)，则p必定是一个质数。
实际上，没有必要测试所有的小于p的自然数，只要测试所有的小于p的质数就可以了。
这个算法的缺点是它非常慢，运算率高；但是它很适合在计算机上面运行程序进行验算一个数是否是质数。
（一）准备知识：
引理1．若a,b,c为任意3个整数，m为正整数，且(m,c)=1,则当ac≡bc(mod m)时，有a≡b(mod m)
证明：ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)因为(m,c)=1即m,c互质，c可以约去，a–b≡0(mod m)可得a≡b(mod m)
引理2．若m为整数且m>1,a1,a2,a3,a4,…a m为m个整数，若在这m个数中任取2个整数对m不同余，则这m个整数对m构成完全剩余系。
证明：构造m的完全剩余系（0,1,2,…m-1），所有的整数必然是这些整数中的1个对模m同余。取r1=0,r2=1,r3=2,r4=3,…r i=i-1,1令(1)：a 1≡r 1(mod m ),a 2≡r 2(mod m ), …a m ≡r m (mod m )(顺序可以不同),因为只有在这种情况下才能保证集合{a 1,a 2,a 3,a 4,…a m }中的任意2个数不同余，否则必然有2个数同余。由式(1)自然得到集合{a 1,a 2,a 3,a 4,…a m }对m 构成完全剩余系。
引理3．设m 是一个整数，且m >1，b 是一个整数且(m ,b )=1。如果a 1,a 2,a 3,a 4,…a m 是模m 的一个完全剩余系，则ba 1,ba 2,ba 3,ba 4,…ba m 也构成模m 的一个完全剩余系。
证明：若存在2个整数ba i 和ba j 同余即ba i ≡ba j (mod m )，
根据引理1则有a i ≡a j (mod m )。根据完全剩余系的定义可知这是不可能的，因此不存在2个整数ba i 和ba j 同余。由引理2可知ba 1,ba 2,ba 3,ba 4,…ba m 构成模m 的一个完全剩余系。
引理4．如果a ,b ,c ,d 是四个整数，且a ≡b (mod m ),c ≡d (mod m ),则有ac ≡bd (mod m )
证明：由题设得ac ≡bc (mod m ),bc ≡bd (mod m )，由模运算的传递性可得ac ≡bc (m od 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)，显然W ≡W (mo d p )。令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)(mod p )即W *a p -1≡W (mod p )。易知(W ,p )=1，由引理1可知a p -1≡1(mod p ）
二、典型例题：
例1 设n 为正整数.证明：373n n +的充要条件是1373+n n .
证明 若 337n n +，
则 7|n ，
于是，由Fermat 小定理，知
),7(mod 16≡n
从而，由 337n n +，
知 33)3(7n n n +，
故 .1373+n n
反过来，若 ,1373
+n n
则 7|n ，
并且 337(31)n n n +⋅，
即 6373n n n ⋅+，
利用Fermat 小定理知 ),7(mod 16≡n
故 .373n n +
命题获证。
说明 涉及指数的同余式经常需要用到Fermat 小定理，因为由Fermat 小定理得出的结论中，同余式的一边是1，这带来很大的方便.
例2 由Fermat 小定理知，对任意奇质数p ，都有).(mod 12
1p p ≡-问：是否存在合数n ，使得)(mod 121n n ≡-成立？
解 这样的合数n 存在，而且有无穷多个.其中最小的满足条件的合数3111341⨯==n （它是从两个不同奇质数作乘积去试算出来的）.
事实上，由于 11210=- ,3341023⨯=
故 ),341(mod 1210
≡ 所以 ),341(mod 11234340≡≡
故341符合要求.
进一步，设a 是一个符合要求的奇合数，则12-a 是一个奇合数（这一点利用因式分解可知）。再设,121q a a ⨯=--q 为正奇数，则
1212)12(2112-=----a a
122-=aq
1)2(2-=q a
112-≡q
).12(mod 0-≡a
因此12-a 也是一个符合要求的数.依此类推（结合341符合要求），可知有无穷多个满足条件的合数.
说明 满足题中的合数n 称为“伪质数”，如果对任意1),(=n a 都有)(mod 11n a
n ≡-成立，那么合数n 称为“绝对伪质数”.请读者寻找“绝对伪质数”.
例3 设p 为质数.证明：存在无穷多个正整数n ，使得n p n -2.
证明 如果2=p ，那么取n 为偶数，就有n p n -2，命题成立.
设2>p ，则由Fermat 小定理知
).(mod 12
1p p ≡- 因此，对任意正整数k ，都有 ),(mod 12)
1(p p k ≡-
所以，只需证明存在无穷多个正整数k ，使得
)(mo d 1)1(p p k ≡-（这样，令),1(-=p k n 就有)2n p n -.
而这只需),(mod 1p k -≡这样的k 当然有无穷多个.
所以，命题成立.
说明 用Fermat 小定理处理数论中的一些存在性问题有时非常方便、简洁.
