浅谈欧拉函数

前言

很早之前就已经接触过欧拉函数这个知识,不久之前也学习了利用筛法求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); 
        }
    }
}

后记

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

上一篇:题解 P2158 【[SDOI2008] 仪仗队】


下一篇:欧拉函数和逆元