下载掌阅APP，畅读海量书库
立即打开
对任意给定的正整数 n ，试求小于 n 且与 n 互素的正整数的个数。
即使从现代数学的角度来看，这个问题仍然是数论中的一个基本问题，它的价值在于由此产生了一个非常有用的数论函数。早在1640年10月18日，费马在给朋友的一封信中叙述了一个数论结果：如果 p 为素数，则对每个正整数 a ，均有 p 整除 a p - a 。后人把费马发现的这个漂亮的结论称为费马小定理。到了1736年，欧拉给出了费马小定理的严格证明。事实上，至今为止人们已经找到了这个定理的许多证明，但值得赞赏的是，欧拉在1760年给出了费马小定理的重要推广。他首先考虑了小于给定正整数 n 且与 n 互素的正整数的个数，高斯为此还专门引进了一个记号 φ （ n ），即 φ （ n ）表示在1，2，…， n 中与 n 互素的正整数的个数，现在称之为欧拉函数。使用这个新的数论函数，欧拉证明了如果 a 和 n 互素，则 n 整除 a φ （ n ） -1。注意到当 n 为素数 p 时，每个小于 p 的正整数都和 p 互素，亦即 φ （ p ）= p -1，此时的欧拉定理变为对每个与 p 互素的 a ，均有 p 整除 a p -1 -1，自然也整除 a p - a 。如果 a 与 p 不互素，亦即 p 整除 a ，则显然有 p 整除 a p - a 。这其实就是费马小定理的内容，因此欧拉的定理的确包含了费马小定理。
令人惊奇的是，欧拉定理的困难之处仅仅在于它的提出和发现，这需要一定的想象力，而它的证明却非常简单。叙述如下：
假设 a 和 n 互素，并且在1，2，…， n 中与 n 互素的正整数为 r 1 ， r 2 ，…， r k ，按欧拉函数的定义，其中 k = φ （ n ）。接着，欧拉又考虑了 k 个数
ar 1 ， ar 2 ，…， ar k
分别除以 n 后所得的余数。一方面，因为 a 和每一个 r i 分别与 n 互素，从而它们的乘积 ar i 也和 n 互素，除以 n 所得的余数也将和 n 互素。另一方面，如果某两项 ar i 和 ar j 除以 n 所得的余数相同，则 n 必整除它们的差 ar i - ar j = a （ r i - r j ）。同样根据 a 和 n 互素的假设，可知 n 整除 r i - r j ，只有 r i = r j 。由此表明上述数列 ar 1 ， ar 2 ，…， ar k 除以 n 所得的余数不仅与 n 互素而且两两不同，故为 r 1 ， r 2 ，…， r k 的一个排列。所以， n 整除下述乘积之差
（ ar 1 ）（ ar 2 ）…（ ar k ）- r 1 r 2 … r k =（ r 1 r 2 … r k ）（ a k -1）。
又因为乘积 r 1 r 2 … r k 也和 n 互素，从而 n 整除 a k -1。至此就完成了欧拉定理的证明。
现在继续讨论欧拉函数 φ （ n ）。既然该函数在数学的许多领域里经常出现，是一个十分基本的数论函数，那么，如何计算 φ （ n ）或者得到它的表达式，则是一个重要的基础问题。前面已经提到过，当 n 为素数 p 时 φ （ p ）= p -1。一般地，当 n 为一个素数幂 p e 时，从定义出发也能求出相应的函数值 φ （ p e ）。事实上，在小于或等于 p e 的正整数中，与 p e 不互素者恰为 p 的倍数，它们只能是
1· p ，2· p ，3· p ，…， p e -1 · p ，
一共有 p e -1 个。这就证明了在小于或等于 p e 中，与 p e 互素的正整数的个数恰为 p e - p e -1 。换句话说，即证明了当 p 为素数时，
φ （ p e ）= p e - p e -1 = p e -1 （ p -1）。
因为任意大于1的正整数均可写成不同的素数幂之积，即可令
，所以，为了计算相应的
φ
（
n
），人们自然期望
φ
（
n
）为积性函数，即对互素的正整数
m
和
n
，总有
φ
（
mn
）=
φ
（
m
）
φ
（
n
）。一旦这个乘积公式得到了证明，借此就能得到
φ
（
n
）的计算公式，亦即
令人感到欣慰的是， φ （ n ）的确是一个积性函数，下面就来证明这一点。
假设 m 和 n 是两个互素的正整数，把从1~ mn 的正整数按下述方式排列成一个有 m 行和 n 列的阵势：
显然，此阵势的第 r （1≤ r ≤ m ）行的 n 个数为
r m + r 2 m + r …（ n -1） m + r 。
一方面，不难看出一个数 d 整除 m 和 r ，当且仅当 d 整除 m 和 km + r 。由此表明当 r 和 m 互素时，第 r 行中的各数也都与 m 互素；而当 r 和 m 不互素时，第 r 行中的每个数也都与 m 不互素。另一方面，假如该行中某两个数 am + r 和 bm + r 除以 n 的余数相同，则它们的差等于（ a - b ） m 也能被 n 整除。从 m 和 n 互素的假定可知 n 整除 a - b ，因为 a 和 b 的取值范围都是从0~ n -1，所以只能是 a = b 。这说明每行中的 n 个数分别除以 n 后所得的余数两两不同，这 n 个不同的余数只能是0，1，…， n -1的一个排列，因而每行中恰有 φ （ n ）个数与 n 互素。注意到与 mn 互素的数就是那些分别同 m 和 n 都互素的数，所以，为了在上述阵势中寻找所有与 mn 互素的数，可以先找出与 m 互素的那些行，共有 φ （ m ）个，然后在每个与 m 互素的行中再接着找出与 n 互素的数来。按以上说明，每行中都恰好有 φ （ n ）个与 n 互素的数。这样，在上述阵势里与 mn 互素的数就共有 φ （ m ） φ （ n ）个，亦即证明了 φ （ mn ）= φ （ m ） φ （ n ）。
至此就介绍完了欧拉函数 φ （ n ）的计算公式及其证明过程，从理论上说解决了 φ （ n ）的计算问题。例如，为了计算 φ （100），即100以内与100互素的数的个数，先把100分解成素数幂乘积100=2 2 ·5 2 ，分别算出 φ （2 2 ）=2以及 φ （5 2 ）=5（5-1）=20，最后得到 φ （100）= φ （2 2 ） φ （5 2 ）=40。但是，当 n 较大，尤其是当 n 的素数幂分解难以写出时，就无法直接应用 φ （ n ）的计算公式，相应的函数值 φ （ n ）也就难以计算了，这也是欧拉函数的美中不足之处。剩下的问题是：对欧拉函数 φ （ n ）而言，能否找到一个不依赖于 n 的因子分解的计算方法呢？遗憾的是，这个问题至今尚未得到解决。
最后，在本问题结束之前，再证明欧拉函数的一个基本性质：设 m 为正整数，用记号 a | b 表示 a 整除 b ，则
该证明是高斯首先给出的。对 m 的每个因子 d ，记 C d 为1，2，…， m 中那些与 m 的最大公因子为 d 的正整数集合。注意到 n 在 C d 中当且仅当（ m ， n ）= d ，亦即（ m / d ， n / d ）=1。此时 n / d 的取值共有 φ （ m / d ）个，表明 C d 中元素的个数为 φ （ m / d ）。显然1，2，…， m 中的每个元素恰属于一个集合 C d ，所以
