下载掌阅APP，畅读海量书库
立即打开
现在我们终于可以利用前面所得到的结论，来证明费马小定理了：
如果p是素数，那么对于满足0＜a＜p的任何一个a来说，a p-1 -1都可以为p所整除。
证明 考虑表达式
把连乘的各项所具备的a都提取出来，这样就得到：
威尔逊定理可以写为：
将上面这种写法代入等式（5.2）中，就得到：
现在重新观察表达式
我们可以将其展开，并将连乘的各项视为一个集合，也就是{a，2a，3a，…，（p-1）a}，而根据余数排列引理（参见引理5.1），该集合相当于{q
1
p+r
1
，…，q
p–1
p+r
p–1
}，因此：
把等式右侧的连乘展开之后，我们会得到许多个带有p的项，以及一个由全体r i 相乘所形成的项。如果将前面那些项中的p值提取出来，并把这些项合起来记为up，那么等式右侧就可以写为up与所有的r i 相乘之和：
现在对等式右侧运用威尔逊定理，并把p的倍数合并为一项，这样就得到：
其中w=u+v+1。由于等式（5.3）与等式（5.4）所描述的是同一个
因此这两个式子的右侧是相等的。对此稍作变换，即可得到：
把等号右边各项中的p提取出来，就可以得出我们想要证明的结果：
由此可见，a p-1 -1能够为p所整除。
由于a p-2 ·a=a p-1 ，而根据费马小定理，又有a p-1 =mp+1，因此，在模p运算之下，a p-2 与a互为乘法逆元素。（两数关于p互为乘法逆元素，意思就是说，这二者的乘积与p相除，余数是1。）
那么，费马小定理的逆定理又该如何证明呢？要想证明此定理，我们还得借助另外一项结论：
引理5.4（不可逆引理） 如果n=uv，且u，v＞1，那么u在模n运算下就是不可逆的。
证明 令n=uv，并假设可以找到一个与u互逆的数w，也就是说，wu=mn+1。那么：
如果定义z=（w-mv），那么：
而由于n＞v，因此zn＞v，这与zn=v相矛盾。由此可见，证明开始处所做的假设是不成立的，u不可能具有乘法逆元素。
定义5.1 如果gcd（m，n）=1，那么m与n互质（coprime）。也可以说成：如果m与n没有大于1的公因子，那么两数互质。
如果n不是素数，那么在模n运算之下，根据不可逆引理可知：其中有些元素可逆，有些元素不可逆。那些不与n互质的元素，是不可逆的。
定理5.6（费马小定理的逆定理） 对于满足0＜a＜n的所有a值来说，如果：
那么n是素数。
证明 假设n不是素数，则有n=uv。根据不可逆引理，u是不可逆的。然而根据该定理的条件可知：u n-1 =u n-2 u=1+q u n，这表明u与u n-2 互为乘法逆元素，因此u是可逆的。这两个结论互相矛盾。由此可见，证明开始处所做的假设不成立，n必定是素数。