积性函数系列（一）：欧拉函数

本文主要是介绍积性函数系列（一）：欧拉函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本系列是数论篇章的第一篇（于是又挖了一个数论的坑orz），主要介绍、证明初等数论中一些重要的概念、结论。
在微积分学领域，积性函数指的是具有 f(ab)=f(a)f(b) 的函数，在数论领域这个概念略有不同，仅定义在正整数上，它揭示了整数的很多性质。废话不多说，直奔主题。

为了区分通常意义上的函数，我们定义算数函数：

定义1.1 定义在所有正整数上的函数称为算数函数。
在整个积性函数篇里，不加说明地，我们总是讨论算数函数。

定义1.2 算术函数 f 如果满足对于任意两个互质的正整数 m 和 n ，均有 f(mn)=f(m)f(n) ，就称 f 为积性函数（或乘性函数）。如果对于任意两个正整数 m 和 n ，均有 f(mn)=f(m)f(n) ，就称为完全积性函数。

很容易找到一些trivial的积性函数，如 f(n)=1,f(n)=n,f(n)=n2 ，事实上所有的幂函数都是积性函数。

结合积性函数的定义和算数基本定理，很容易得到下面的定理：

定理1.1 如果 f 是一个积性函数，对于任意的正整数 n 有素数幂分解 n=p1a1p2a2...psas ，那么有 f(n)=f(p1a1)f(p2a2)...f(psas)
证明：略，使用数学归纳法即可。

好了，介绍完了积性函数的基本概念，就开始介绍今天的主角，欧拉函数，它也被称为欧拉 ϕ 函数。顾名思义，它是由欧拉首先研究的。

定义1.3 欧拉函数 ϕ(n) 定义为不超过 n 且和 n 互质的正整数的个数。

下面我们就来探讨欧拉函数在各个点上的取值。很容易得到对于素数 p ， ϕ(p)=p−1 ，那么反过来是不是也成立呢？

定理1.2 如果 p 是素数，那么 ϕ(p)=p−1 .反之，如果 p 是正整数且满足 ϕ(p)=p−1 ，那么 p 是一个素数。
证明：前句可由互质定义得到，我们只证明后句。若 p 不是素数，那么或是1或是合数。而 ϕ(1)=1 ，但若 p 是合数，得有因子 0<d<p ,而 p 不与自身互质，这使得和 p 互质的数至多只有 p−2 个，所以也不可能，故 p 是素数。

我们再进一步，看欧拉函数在素数的幂下的取值。实际上和素数幂 pn 不互质的只有 p 的倍数，一共有 pn/p=pn−1 个，故 ϕ(pn)=pn−pn−1 。

定理1.3 如果 p 是素数，那么 ϕ(pn)=pn−pn−1 。

接下来我们讨论更一般的情况，为此，我们需要证明欧拉函数是一个积性函数。定理的证明依赖于同余的一些简单性质，由于本文是本系列的第一篇，所以这里尽量把需要用到的性质先给证一证。如果你对这些性质比较清楚，可以直接跳过下面的补充部分，直接进入定理的证明。

定义1.4 一个模 m 完全剩余系是一个整数的集合，使得任意整数恰和此集合中的一个元素模 m 同余。

引理1.4 m 个模 m 不同余的整数的集合构成一个模 m 的完全剩余系。
证明：假设 m 个模 m 不同余的整数的集合不是一个模 m 的完全剩余系。那么可能存在整数 a ，使得集合中存在不止一个元素和 a 同余，但由于同余的性质，如果 a 和 b 模 m 同余，且 a 和 c 模 m 同余，那么必有 b 和 c 模 m 同余，和假设不符；那么可能存在整数 a ，使得集合中不存在元素和 a 同余，但模 m 的余数只有 m 种可能， a 否定了一种可能，意味着集合里的元素模 m 至多只有 m−1 个值，但集合中的 m 个元素互不同余，应有 m 个不同的值，和假设不符。故原假设成立。

由上述引理，容易得到 0,1,2,3,...,m−1 是模 m 的一个完全剩余系。

引理1.5 若 r1,r2,...,rm 是模 m 的一个完全剩余系，且正整数a满足 gcd(a,m)=1 ,则对任意整数b， ar1+b,ar2+b,...,arm+b 都是模 m 的完全剩余系。
证明：由引理1.4，我们只需证明这m个数互不同余。取任意两个元素 ri,rj,i≠j 相减，得 ari+b−(arj+b)=a(ri−rj) .
若我们有 ari≡arj(mod m) , 基于同余的性质，在 gcd(a,m)=1 的情况下，两边可以约去 a ，于是得到 ri≡rj(mod m) ，这和假设矛盾，故 ari,arj 不同余，故引理成立。

有了引理1.5后，我们就可以比较方便地证明定理1.6。

定理1.6 设m,n是两个互质的正整数，那么 ϕ(mn)=ϕ(m)ϕ(n) .
证明：我们将 1,2,...,mn 从上往下，从左往右依次排列，每一列写m个数：
1  m+1 2m+1 ... (n−1)m+1
2  m+2 2m+2 ... (n−1)m+2
...
r  m+r 2m+r ... (n−1)m+r
...
m  2m  3m     ...  nm
从行的角度观察上式，考察第 r 行，由于 m 和 m 不互质，所以如果 r 不和 m 互质的话，整行都不与 mn 互质，所以实际上我们只需考虑 ϕ(m) 行。而对于这些 r 和 m 互质的行，每一行实际上构成模 n 的完全剩余系，我们研究某行，为了方便，同样记为 r 。取第 k 个元素，即 (k−1)m+r ，记 (k−1)m+r mod m=d .
如果d和m互质，那么有 (k−1)m+r−d=λm 可知， (k−1)m+r 和 m 也互质，否则存在的因子必是 d 的因子（同除以该因子，两边应均为整数）；反之，如果 d 和 m 不互质， (k−1)m+r 和 m 也不互质， d 和 m 的公因子也是它们的公因子。于是每一行都有 ϕ(n) 个因子。定理得证。

结合定理1.3和定理1.6，以及算数基本定理，我们可以求得任意正整数的欧拉函数值。

定理1.7 设 n=p1a1p2a2...pkak 为正整数n的素数幂分解，那么 ϕ(n)=n(1−1/p1)(1−1/p2)...(1−1/pk) .
证明：由定理1.1和1.6可得， ϕ(n)=ϕ(p1a1)ϕ(p2a2)...ϕ(pkak) .由定理1.3可得， ϕ(pkak)=pk−pk−1 ，于是有
ϕ(n)=p1a1p2a2...pkak(1−1/p1)(1−1/p2)...(1−1/pk)
=n(1−1/p1)(1−1/p2)...(1−1/pk)

至此我们已经掌握了欧拉函数的值得求法。你是否对这么多的证明感到厌烦了，在进一步讨论欧拉函数的性质之前，我们转换一下角度，从程序设计的角度入手，看看如何实现计算欧拉函数。如果你对程序设计不感兴趣，可以直接跳过这部分内容。计算单个欧拉函数值的过程实际上就是对正整数 n 进行分解的过程，我们从2开始从小到大寻找 n 的因子，显然找到的最小的因子必是素数（否则会有更小的素因子），找到后把这个素因子全部约去，并计算 (1−1/p1) ，然后接着向前，由于之前的因子已经消去，我们仍能保证找到的因子是素数。完整的代码如下：

int euler(int x){
 
    int res = x;
 
    for(int i=2; i<(int)sqrt(x*1.0)+1; ++i)
 
        if(x % i == 0){
 
             res = res / i * (i - 1);
 
             while(x % i == 0) x /= i;
 
         }
 
    if(x > 1) res = res / x * (x - 1);
 
    return res;
 
}

下面给出求 1..maxn 的所有欧拉函数值的程序，也非常简单，这里不再解释了。

for(int i=1; i<=maxn; ++i) phi[i] = i;
 
for(int i=2; i<=maxn; i+=2) phi[i] /= 2;
 
for(int i=3; i<=maxn; i+=2)
 
    if(phi[i] == i){
 
        for(int j=i; j<=maxn; j+=i)
 
            phi[j] = phi[j] / i * (i - 1);
 
    }

短暂的休息之后接着回到欧拉函数的性质中来。下面的定理表明，除了 n=1,2 ， ϕ(n) 都是偶数。

定理1.8 设 n 是一个大于2的正整数，那么 ϕ(n) 是偶数.
证明：由定理1.1和1.2可知，大于2的素数都是偶数，而所有高于1次的素数幂（包括2）都是偶数，而由定理1.7，所有大于2的合数的欧拉函数都可以分解成素数幂的乘积，所以也必定是偶数。

最后我们介绍一个非常重要的概念，和函数，它在后续的内容中也会发挥作用。

定义1.5 设 f 是一个算数函数，那么记 F(n)=∑d|nf(d) 代表 f 在 n 中所有正因子处的值的和，则 F 称为 f 的和函数。

对于欧拉函数而言，它的和函数有很好的性质：

定理1.9 设 n 为一个正整数，那么 ∑d|nϕ(d)=n .
证明：我们1..n的整数按照与n的最大公约数划分成若干个不相交的类，最大公约数为d的类记为 Cd 。那么 m∈d 当且仅当 gcd(n,m)=d ，或者说 gcd(n/d,m/d)=1 ，由于 1<=m<=n ， m/d 可以取到 1..n/d 的所有数，于是符合条件的m的个数即为 ϕ(n/d) 。于是有
F(n)=∑d|nf(n/d) ,而 n/d 实际上取尽了n的所有因子，于是等价于 ∑d|nf(d) ，定理得证。