下载掌阅APP，畅读海量书库
立即打开
现在我们来看看与消去（cancellation）这一概念有关的一些结论。如果x与y互为乘法逆元素（也就是互为倒数），那么这两者相乘之后就会消去，或者说，两者的乘积是1。
我们可以通过模运算（modular arithmetic）来理解消去这一概念，这种运算是由高斯（Carl Gauss）所引入的，本书第8章将会介绍他。尽管欧拉在证明费马小定理时并没有用到这项技巧，但该技巧有助于我们理解证明的过程。
十二小时制的钟表能够很好地说明什么叫做模运算。假如现在是10点钟，那么过5个小时之后，就是3点钟。也就是说，10+5=3，或者说得更精确一些：（10+5）mod 12=3。（注意：数学家把正午12点叫做“0”点。）其实模运算可以适用于任意的底数。比方说，如果以7为底数，那么：
请注意，对于上面第二个例子来说，我们也可以先按照普通的办法来做乘法，然后再将乘积表示为7的倍数与某个余数之和：
换句话说，某个值与n取模，就等于该值与n相除的余数。
在初等算术（比方说，有理数的算术）中，如果x与y的乘积是1，那么这两项就可以消去（cancel），我们把x与y分别称为对方的倒数（inverse）。模运算里面也有倒数这个概念，只不过它所涉及的那两个数，都是整数。例如：
我们可以说，2与4能够互相消去，这两个数在模7运算时互为倒数。
如果给x前面添上负号，那么-x mod n的结果，就是n-x，这相当于把钟表“倒拨”了x个小时。尤其值得注意的一条规律是：-1 mod n=n-1。
与初等算术一样，模运算也有乘法表。下面就是一张整数模7运算的乘法表：
首先，我们把两数的普通乘积表示为7的倍数与某个余数之和，然后单独把那个余数提取出来，将其视为这两数相乘并对7取模之后的结果。比方说，由于5×4=20=（2×7）+6=6 mod 7，因此，乘法表第5行与第4列相交汇的那个单元格里面写的数字就是6。我们注意到：每一行中的那六个数字都与另外各行中的六个数字相同，只不过排列顺序有所区别，而且1这个数字在每一行里面都会出现。刚才说过，如果两项的积是1，那么二者互为倒数，由此可见，在上面那张表格里面，2与4互为倒数，因为2×4=1 mod 7。我们现在重新绘制这张乘法表，把每一行左侧的那个数字所对应的倒数写在该行的右侧：
严格地来说，在整数n＞1且整数u＞0的条件下，如果能找到满足uv=1+qn的整数q，那么v就是u在模n运算下的乘法逆元素（模反元素）。换句话说，如果u与v的乘积除以n之后余1，那么两者互为模n运算之下的倒数。接下来的证明过程，很需要依赖于这个概念。
例如下面这项结论，就依赖于这种经过泛化的消去概念：
引理5.2（消去律） 如果p是素数，那么对于满足0＜a＜p的任何一个a来说，都能找到满足0＜b＜p的数b，使得ab=mp+1。
换句话说，a与b在模p运算之下可以互相消去。
仍以p=7且a=4为例。有没有这样的b值能够使等式ab=mp+1成立呢？我们轮流尝试b的各种取值，直到发现可以满足该式的值为止：
证明 将a与集合{1，…，p-1}中的各元素分别相乘：
根据余数排列引理，对于新集合中的各元素来说，必然会有一个元素与p相除之后余1。也就是说，此集合中的元素分别除以p，会产生p-1个互不相同的余数，其中肯定有一个是1。因此，在原集合中，必然可以找到能够与a相互消去的元素b。
请注意，1与p-1属于那种能够自我消去（self-canceling）的元素，也就是说，在模p运算下，该元素与其自身相乘之后的结果是1，或者说，结果可以表示成mp+1的形式。对于1来说，1·1显然可以表示成这种形式，因为它就是0p+1。那么p-1呢？
（p-1） 2 =p 2 -2p+1=（p-2）p+1=mp+1
实际上，在模p运算下，能够自我消去的元素，只有1与p-1这两个。我们现在就要证明这一点。
引理5.3（自我消去律）
对于满足0＜a＜p的任何一个a来说，a
2
=mp+1
a=1∨a=p–1。
证明 假设除了1与p-1之外，还有一个元素a也可以自我消去，那么：
对引理中所述的条件进行变换，可以得到：
对等式左边做分解：
根据我们所做的假设可知，0＜a-1，a+1＜p，这意味着两个小于p的整数相乘，其积可以为p所整除。这与《几何原本》第7卷第30号命题相矛盾（参见定理5.4）。因此，证明开始处所做的假设是不成立的，也就是说，在模p运算下，只有1与p-1这两个元素能够自我消去。
证明费马小定理所需的准备工作差不多已经完成了，然而在开始证明之前还需要了解最后一项结论，这就是威尔逊定理（Wilson’s theorem）。该定理由爱德华·华林（Edward Waring）于1770年提出，并以其学生约翰·威尔逊（John Wilson）来命名。华林当时说他没办法证明这条定理，因为他找不到适当的符号，高斯后来对此评论道：“需要的不是符号，而是概念”。
定理5.5（威尔逊定理） 如果p是素数，那么可以找到满足下列等式的整数m：
也可以说：
证明 根据阶乘的定义可知：
根据消去律，对于1至p-1之间的每个数a来说都能找到同一个范围内的数b，使得a与b可以互相消去，而根据自我消去律，只有1与p-1这两个数可以同它自身相抵消。由此可见，在连乘的各数中，1与p-1之外的元素都能够分别与某个不同于自身的乘法逆元素相消去，也就是说，那些数的乘积与p相除其余数是1。这意味着我们可以找到某个数n，从而将1至p-1之间那些彼此消去的项所构成的积，合起来表示为np+1的形式。于是，刚才的多项连乘现在就变为三项相乘，其中两项是尚未消去的1与p-1，另外一项是np+1：
由此可见，我们确实能够找到符合定理要求的m值，此时m=np-n。
习题5.1 证明：如果n是大于4的合数，那么（n-1）！是n的倍数。