浅谈欧拉函数

2021年9月10日 5点热度 0条评论 来源: 反演的莫比乌斯环

前言

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

后记

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

    原文作者:反演的莫比乌斯环
    原文地址: https://www.cnblogs.com/Mobius-strip/p/15248002.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。