欧拉函数|(扩展)欧拉定理|欧拉反演

忘是亡心i 2021-11-09 20:06 447阅读 0赞

[也许更好的阅读体验][Link 1]

# 欧拉函数 #

*  欧拉函数是 **小于** n的数中与n **互质** 的数的 **数目**  
    符号\\(\\varphi(x)\\)  
    **互质** 两个互质的数的最大公因数等于1,1与任何数互质
 *  通式  
    \\(\\varphi(x)=x\\prod\_\{i=1\}^n(1-\\frac\{1\}\{p\_i\})\\)  
    其中\\(p\_i\\)为\\(n\\)的质因子

--------------------

# 常用性质 #

*  若\\(n\\)为质数，显然\\(\\varphi(n)=n-1\\)  
    \\(\\begin\{aligned\}\\end\{aligned\}\\)
 *  **欧拉函数是积性函数**  
    积性函数: 对于任意 **互质** 的整数\\(a\\)和\\(b\\)有性质\\(f(ab)=f(a)·f(b)\\)的数论函数。  
    若\\(m,n\\)互质，\\(\\varphi(mn)=\\varphi(m)·\\varphi(n)\\)  
    \\(\\begin\{aligned\}\\end\{aligned\}\\)
 *  如果\\(x=2n\\)(\\(n\\)为奇数)，\\(\\varphi(x)=\\varphi(n)\\) 即\\(\\varphi(2n)=\\varphi(n)\\)(\\(n\\)为奇数)  
    n为奇数时,n与2互质，\\(\\varphi(2)=1\\)  
    \\(\\begin\{aligned\}\\end\{aligned\}\\)
 *  若\\(p\\)为质数,则\\(\\varphi(p^k)=p^k-p^\{k-1\}\\)  
    因为与\\(p^k\\)不互质的只有\\(p\\)的倍数，而\\(p^k\\)中\\(p\\)的倍数有\\(p^\{k-1\}\\)个  
    \\(\\begin\{aligned\}\\end\{aligned\}\\)
 *  当\\(x>2\\)时，\\(\\varphi(x)\\)为偶数  
    这一点需要了解更相减损术 即\\(gcd(n,x)=gcd(n,n-x)\\)  
    由该公式我们可以知道，所有与\\(n\\)互质的数都是成对出现的  
    \\(\\begin\{aligned\}\\end\{aligned\}\\)
 *  小于n的数中，与n互质的数的总和为\\(\\varphi(n)\*n/2\\ \\ (n>1)\\)  
    由上面的证明(更相减损术)我们知道，每一对与\\(n\\)互质的数的和为\\(n\\)，共有\\(\\varphi(n)/2\\)对  
    \\(\\begin\{aligned\}\\end\{aligned\}\\)
 *  \\(n=\\sum\_\{d|n\}\\varphi(d)\\)即\\(n\\)的因数\\((\\)包括\\(1\\)和它自己\\()\\)的欧拉函数之和等于\\(n\\)  
    这条性质的运用又叫 **欧拉反演**  
    定义函数  
    \\(\\begin\{aligned\}f(n)=\\sum\_\{d|n\}\\varphi(d)\\end\{aligned\}\\)
    
     *  \\(f(n)\\)为积性函数  
        \\(\\begin\{aligned\}f(n)·f(m)=\\sum\_\{i|n\}\\varphi(i)\\sum\_\{j|m\}\\varphi(j)=\\sum\_\{i|n\}\\sum\_\{j|m\}\\varphi(i)·\\varphi(j)=\\sum\_\{i|n\}\\sum\_\{j|m\}\\varphi(i·j)=\\sum\_\{d|nm\}\\varphi(d)=f(nm)\\end\{aligned\}\\)
    
    \\(f(p^k)=\\varphi(1)+\\varphi(p)+\\varphi(p^2)+\\cdots+\\varphi(p^k)=1+(p-1)+(p^2-p)+\\cdots+(p^k-p^\{k-1\})=p^k\\)
    
    \\(n=p\_1^\{k\_1\} ·p\_2^\{k\_2\}· \\cdots·p\_m^\{k\_m\}\\)
    
    \\(f(n)=f(p\_1^\{k\_1\})·f(p\_2^\{k\_2\})·\\cdots·f(p\_m^\{k\_m\})=p\_1^\{k\_1\} ·p\_2^\{k\_2\}· \\cdots·p\_m^\{k\_m\}=n\\)  
    \\(\\begin\{aligned\}\\end\{aligned\}\\)

--------------------

# 欧拉定理 #

若\\(a,m\\)互质，\\(a^\{\\varphi(m)\}≡1(mod\\ m)\\)

*  证明
    
     *  **剩余系** 指对于某一个特定的正整数\\(n\\)，一个整数集中的数\\(mod\\ n\\)所得的余数域。
     *  **完全剩余系** 设\\(m\\in Z+\\)，若\\(r\_0,r\_1,...r\_\{m−1\}\\)为\\(m\\)个整数，并且两两模\\(m\\)不同余，则\\(r\_0,r\_1,...r\_\{m−1\}\\)叫作模\\(m\\)的一个完全剩余系。
     *  **缩系** 设\\(A\\)是\\(mod\\ n\\)的剩余系，若任意\\(A\\)中两个元素相乘\\(mod\\ n\\)后仍为\\(A\\)中的元素,则称\\(A\\)为\\(mod\\ n\\)的缩系
     *  若\\(a,m\\)互质，则\\(m\\)的一个缩系为\\(\\\{a,2a,3a...\\varphi(m)a\\\}\\)  
        \\(\\varphi(m)! ≡ \\prod^\{\\varphi(m)\}\_\{i=1\}a\_i(mod\\ m)\\)  
        \\(\\varphi(m)! ≡ a^\{\\varphi(m)\}·\\varphi(m)!(mod\\ m)\\)  
        \\(a^\{\\varphi(m)\}≡1(mod\\ m)\\)
        
         *  而当\\(m\\)为质数时，\\(\\varphi(m)=m-1\\)  
            \\(a^\{(m-1)\}≡1(mod\\ m)\\)  
            这就是我们熟知的 **费马小定理**

--------------------

# 扩展欧拉定理 #

若\\(b>\\varphi(m)\\) 即使\\(a,m\\)**不互质**，\\(a^b≡a^\{b \\%\\varphi(m)+\\varphi(m)\}\\)

*  证明  
    从\\(m\\)中提一个质因子\\(p\\)出来 令\\(m=p^k·s\\)  
    有\\(gcd(p^k,s)=1\\)，即\\(p^k,s\\)互质  
    根据欧拉定理，我们知道\\(p^k≡p^\{\\varphi(s)\}≡1(mod\\ s)\\)  
    根据欧拉函数是积性函数，我们知道\\(\\varphi(s)|\\varphi(m)\\)所以有\\(p^\{\\varphi(m)\}≡p^\{\\varphi(s)\}(mod\\ s)\\)  
    设\\(p^\{\\varphi(s)\}=xs+1\\)  
    那么\\(p^\{\\varphi(s)+k\}=xm+p^k\\)  
    所以\\(p^\{\\varphi(s)+k\}≡p^k (mod\\ m)\\)，也有\\(p^\{\\varphi(m)+k\}≡p^k (mod\\ m)\\)  
    当\\(b>=k\\)时，\\(p^b≡p^\{b-k\}·p^k≡p^\{b-k\}·p^\{\\varphi(s)+k\}≡p^\{b+\\varphi(m)\}(mod\\ m)\\)  
    又因为\\(k<=\\varphi(p^k)<=\\varphi(m)\\)，所以当\\(b>=2\\varphi(m)\\)时，满足\\(p^b≡p^\{b-\\varphi(m)\}(mod\\ m)\\)  
    注意是\\(2\\varphi(m)\\)!  
    所以可以得到\\(p^b≡p^\{b\\%\\varphi(m)+\\varphi(m)\}(mod\\ m)\\)  
    因此我们可以得到对任意质数\\(p\\)都有\\(b>=2\\varphi(m),p^b≡p^\{b\\%\\varphi(m)+\\varphi(m)\}(mod\\ m)\\)  
    非\\(m\\)质因子的\\(p\\)，有欧拉定理  
    将\\(a\\)因式分解，可以得到  
    \\(a^b≡a^\{b\\%\\varphi(m)+\\varphi(m)\}(mod\\ m)\\)
    
     *  注意 \\(b<\\varphi(m)\\)时，公式不一定成立

--------------------

# 线性筛法 #

类似与筛素数，我们在这里利用欧拉函数是积性函数这个性质来筛\\(\\varphi\\)  
**\\(\\mathcal\{Code\}\\)**

int cnt;
    int prime[maxn],phi[maxn];
    bool vis[maxn];
    void Euler_sieve (int n)
    int cnt;
    int prime[maxn],phi[maxn];
    bool vis[maxn];
    void Euler_sieve (int n)
    {
        phi[1]=1;
        for (int i=2;i<=n;++i){
            if (!vis[i])    prime[++cnt]=i,phi[i]=i-1;
            for (int j=1;j<=cnt&&i*prime[j]<=n;++j){
                vis[i*prime[j]]=true;
                if (i%prime[j]==0){ phi[i*prime[j]]=phi[i]*prime[j];break;}
                phi[i*prime[j]]=phi[i]*phi[prime[j]];
            }
        }
    }

--------------------

# 欧拉反演 #

利用欧拉函数的一条性质  
\\(\\begin\{aligned\}n=\\sum\_\{d|n\}\\varphi(d)\\end\{aligned\}\\)  
(上面有证明)  
我们试着把\\(n\\)换成其他东西试试  
\\(\\begin\{aligned\}gcd(i,j)=\\sum\_\{d|gcd(i,j)\}\\varphi(d)=\\sum\_\{d|i\}\\sum\_\{d|j\}\\varphi(d)\\end\{aligned\}\\)  
让我们求个东西试试  
\\(\\begin\{aligned\}\\sum\_\{i=1\}^ngcd(i,n)=\\sum\_\{i=1\}^n\\sum\_\{d|i\}\\sum\_\{d|n\}\\varphi(d)=\\sum\_\{d|n\}\\sum\_\{i=1\}^n\\sum\_\{d|i\}\\varphi(d)=\\sum\_\{d|n\}\\frac\{n\}\{d\}\\varphi(d)\\end\{aligned\}\\)  
把它重写一遍作为结论  
\\(\\begin\{aligned\}\\sum\_\{i=1\}^ngcd(i,n)=\\sum\_\{d|n\}\\frac\{n\}\{d\}\\varphi(d)\\end\{aligned\}\\)

--------------------

> 如有哪里讲得不是很明白或是有错误，欢迎指正  
> 如您喜欢的话不妨点个赞收藏一下吧

转载于:https://www.cnblogs.com/Morning-Glory/p/11106828.html

[Link 1]: https://blog.csdn.net/Morning_Glory_JR/article/details/94155283