下载掌阅APP，畅读海量书库
立即打开
与其他那些大数学家一样，欧拉同样不会因为仅仅证明了费马小定理而感到满足，他还想把该定理变得更加通用一些。由于费马小定理只适用于素数，因此，欧拉想看看有没有类似的规律能够把合数也包括进来。然而合数在模运算之下的行为，是有些奇怪的。比方说，下面是一张模10运算的乘法表。每一行左侧的那个数字所对应的乘法逆元素，标注在该行右侧：
这张表格看上去似乎有些眼熟，其实它就是一张普通的10×10乘法表格，只不过仅保留了乘积的个位数而已。比方说，在普通的乘法中，7×9=63，而在模10的乘法中，其结果是3，这恰好是63与10相除的余数。这张表格与模7的那张表格（参见5.3节）相比，有两个显著的区别。第一，每行中的数字未必都与其他各行相同。第二，有些行里面包含0。这是个相当重要的区别，因为从普通乘法的角度来看，两个非零的数相乘，结果怎么可能是0呢？然而在模运算中确实有可能出现两个非零的数相乘等于0的情况，因此，我们必须面这种情况。
早前我们说过，在针对素数的模运算中，只有1和-1这样两个元素是可以自我消去的。尽管这条规律对于10这个合数来说依然成立，但却未必对所有的合数都成立。（比方说，在模8运算之下会出现4个能够自我消去的元素，它们分别是1、3、5、7。）
现在重新来观察模10运算的乘法表，这次我们只关注其中的特定单元格：
如果某一行里面只包含“良好的”乘积（也就是说，该行里面没有0），那么我们就给该行左侧的那个数字加上方框。大家可以看到：这些行左侧所对应的数字，恰好都是拥有乘法逆元素的数字。那么，有哪些数字具备这样的性质呢？只有那些与10互质的数字，才具备这样的性质。（两数互质，意味着它们没有1以外的公因子。）
是不是只需要把仅包含非零乘积的那些行保留下来就可以了呢？不是的，因为这种行内的某些乘积，如果再于其他数相乘，那么依然有可能是0。（比方说，3所对应的那一行，是个良好的行，然而（3×5）×2=0。）欧拉的想法是：只保留良好的行和良好的列相交汇处的那些数字，也就是灰色单元格中的数字。这些数字，与针对素数的模运算中的数字类似。比方说，每一组这样的数字，都与由其他灰色单元格所构成的那些组中的数字相同，只不过排列顺序有所不同，而且每一组里面都含有1。
为了将费马小定理扩展到合数上面，欧拉只选取表格中加粗的那些值。他首先定义互质集的大小：
定义5.2 正整数n的totient是小于n且与之互质的正整数个数。它可以由下列公式来确定：
这叫做 欧拉总计函数 （Euler totient function）或 欧拉φ函数 （Eulerφfunction）。
φ（n）的值，就是模n运算的乘法表中带有灰色单元格的行数。例如对于模10及模7运算来说，分别有φ（10）=4、φ（7）=6，这恰好与各自乘法表中包含灰色单元格的行数相同。
根据素数的定义：任何一个素数与比它小的那些正整数之间，都没有公共的素因子，因此，素数的totient就是：
换句话说，小于给定素数的所有正整数都与该素数互质。
欧拉发现，费马小定理中的p-1，只是φ函数在自变量为素数时的特例而已。于是，欧拉对该定理做了推广。
定理5.7（欧拉定理）
coprime（a，n）
a
φ（n）
-1可以为n所整除。
习题5.2 修改费马小定理的证明过程，以便证明欧拉定理。修改步骤如下：
·在原来使用余数排列引理的地方，改用互质余数排列引理（Permutation of Coprime Remainders Lemma）。（实际上还是沿用同一套证明过程，只不过这次关注的仅仅是那些灰色单元格中的“良好”元素而已。）
·证明每一个与n互质的余数，在模n运算下都有乘法逆元素。（上一步已经证明：这些余数会出现在每一个“良好的”行中，只是排列顺序有所不同。因此，只要1这个元素位于其中，那无论怎么排列，它都会出现在每一个“良好的”行里面。）
·在原来的证明过程中，我们考虑的是所有非零余数之间的乘积，这次将其改为所有与n互质的余数之间的乘积。
我们想找一种办法，来计算任意整数的φ函数值。因为大于2的整数均可以写为素数的幂之间的乘积，所以首先要明白如何针对素数p的幂来计算其totient值，也就是要确定与p m 互质的数有多少个。由于比p m 小的正整数共有p m -1个，因此取值上限是p m -1。在这p m -1个数中，凡是可以为p所整除的数（也就是p的各种倍数）都不与p互质，于是需要把它们从总数中减去：
对于那种可以分解成两个素因子p、q的数来说，φ（p u q v ）的值该怎么计算呢？我们还是像刚才那样，先考虑取值的上限，然后从中排除相关的倍数。这次要先排除p的倍数，再排除q的倍数，然后把那些可以同时为p与q所整除的数恢复过来，以免重复排除。（这个技巧称为容斥原理（Inclusion-exclusion principle），它经常用在组合数学中。）设n=p u q v ，那么：
如果n仅仅是p 1 与p 2 这两个素数直接相乘所得的积，那么作为特例，我们可以得出：
比方说，由于10=5×2，因此：
对于φ函数来说，我们最为关注的自变量，其实就是这种由两个素数直接相乘所构成的值，然而除此之外，还也可以试着对刚才的公式再做一次推广，将其适用范围扩大到两个以上的素数。比方说，如果n有p、q、r这三个素因子，那我们就先排除每一个素因子的倍数，然后把那些可以同时为p、q所整除，同时为p、r所整除，以及同时为q、r所整除的数分别恢复过来，最后再将能够为三者之积pqr所整数的数拿掉，以免重复计算。如果令
那么刚才的公式就可以按照这样的计算方法，推广到m个素因子上面了：
在证明欧拉定理的过程中，欧拉开始考虑一个问题，那就是：怎样确定与n互质的数到底有多少个。这个问题导致了φ函数的诞生。如果能够对某数做素因子分解，那就可以通过φ函数高效地计算出与该数互质之数的个数。