前言

很早之前就已经接触过欧拉函数这个知识，不久之前也学习了利用筛法求1到n之间的所有欧拉函数值。里面用到了一些欧拉函数的性质。出于好奇心，我特意学习欧拉函数性质的一些证明，今天在此分享给大家。

欧拉函数

说到欧拉函数 \(\phi\) ，首先要明确的就是它的定义：
1、欧拉函数是定义在正整数集合上的函数；
2、\(\phi(1)=1\) ；
3、当 \(n\geq 2\) 时，\(\phi(n)\) 表示小于 \(n\) 且与 \(n\) 互质的正整数（包括 \(1\)）个数。
$\quad $ 比如 \(\phi(2)=1, \phi(3)=2, \phi(4)=2\) 。

欧拉函数有几个重要的性质，下面我就详细地讲解与证明。

欧拉函数的性质

性质一

若n为质数，\(\phi(n)=n-1\) 。

这个性质很好证明，因为对于质数 \(n\) ，从 \(1\) 到 \((n-1)\) 中的所有整数都与 \(n\) 互质。

性质二

当 \(gcd(m,n)=1\) 时， \(\phi(mn)=\phi(m)\phi(n)\) 。特别的，若 \(m,n\) 都为质数， \(\phi(mn)=(m-1)(n-1)\) 。

这条性质的证明需要用到中国剩余定理，可以证明 \(\phi\) 为积性函数（指对于所有互质的整数 \(a\) 和 \(b\) 有性质 \(f(ab)=f(a)f(b)\) 的数论函数）。

同样的，用数学归纳法可证，若 \(m_1,m_2,\cdots ,m_n\) 之间两两互质，则

\[\phi(\prod_{i=1}^{n}m_i)=\prod_{i=1}^{n}{\phi(m_i)} \]

性质三

若 \(n=p^k\) ，其中 \(p\) 为质数，则 \(\phi(n)=p^k-p^{k-1}=p^k(1-\frac{1}{p})\) 。

这条性质证明很简单，因为只有 \(p\) 的倍数之外，即 \(1\times p, 2\times p ,\cdots,(p^{k-1}-1)\times p\) ，其余小于 \(n\) 的所有正整数都与 \(n\) 互质。

可以看出，性质一是 \(k=1\) 时的一个特例。

性质四

对于任意一个正整数 \(n\) ，都可以唯一地表示成若干质数乘积的形式，即\(n=\prod_{i=1}^m{p_i^{k_i}}\) （\(p_i\) 为质数），则

\[\phi(n)=n\prod_{i=1}^m{(1-\frac{1}{p_i})} \]

这条可以根据性质二，由于 \(p_i\) 为质数，所以任意 \(p_i^{k_i}\) 与 \(p_j^{k_j}\) 之间两两互质，可得

\[\phi(n)=\prod_{i=1}^m{\phi(p_i^{k_i})} \]

再根据性质三，可继续化简为

\[\prod_{i=1}^m{\phi(p_i^{k_i})}=\prod_{i=1}^{m}{p_i^{k_i}(1-\frac{1}{p_i})} =n\prod_{i=1}^{m}{(1-\frac{1}{p_i})}\]

性质五

若正整数 \(i\%p=0\) ，\(p\) 为质数，则 \(\phi(i\cdot p)=\phi(i) \cdot p\) 。

此条性质便是筛法求欧拉函数的数学基础，有了性质四，此条性质就很好证明了。

设 \(i=\prod\limits_{j=1}^m{p_j^{k_j}}\) ，则 \(\phi(i)=i\prod\limits_{j=1}^m{(1-\frac{1}{p_j})}\) 。
由于 \(i\%p=0\) 且 \(p\) 为质数 ，所以 \(p\) 必然为 \(p_1\) 到 \(p_m\) 中的某一个数，所以 \(i\cdot p\) 的所有质因数依然为 \(p_1,p_2, \cdots,p_n\) ，因此

\[\phi(i \cdot p)=i \cdot p \prod\limits_{j=1}^m{(1-\frac{1}{p_j})} = \phi(i)\cdot p\]

性质六

小于 \(n\) 且与 \(n\) 互质的数之和为 \(n\cdot\frac{\phi(n)}{2}\) 。

证明这条性质只需证明若 \(gcd(n,i)=1\) ，则 \(gcd(n,n-i)=1\) ，这个用反证法即可证明。

证明了这个，就可得小于 \(n\) 且与 \(n\) 互质的数是两两关于 \(\frac{n}{2}\) 对称的,共有 \(\frac{\phi(n)}{2}\) 对这样的数 ，得证。

性质七

说到欧拉函数，不得不提大名鼎鼎的欧拉定理，即
对于互质的两个数 \(a,m\) ，有 \(a^{\phi(m)}\equiv 1(mod\ m)\) 。

费马小定理是欧拉定理的一个特殊情况，即
若 \(p\) 为质数，则 \(a^{p-1}\equiv 1(mod\ p)\) 。

这条定理证明有些复杂，等我以后有空再证。

筛法求欧拉函数

有了上述理论知识，再回到线性筛法求欧拉函数本身，代码也就不难理解了。

最后就贴一段代码吧。

void get_eulers(int n) 
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++) 
    {
        if (!com[i]) 
        {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && i * prime[j] <= n; j++) 
        {
            com[primes[j] * i] = 1;
            if (i % primes[j] == 0) 
            {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            //pj一定是pj * i的最小质因子,而且pj还不包含在i的质因子当中
            phi[primes[j] * i] = phi[i] * (primes[j] - 1); 
        }
    }
}

后记

花了半天，欧拉函数的一些性质的总结终于讲述结束了，感觉本蒟蒻的思维又得到了提升。爆赞！