【数论】欧拉函数与欧拉定理

_GeorgeAAAADHD_ · 2024-06-04 12:36:53 · 个人记录

本篇博文将对欧拉函数与（扩展）欧拉定理的定义，性质与求法进行讲解。

Part 1. 定义

• 对于一个正整数 n，其欧拉函数 \varphi(n) 表示小于等于 n 的正整数中与 n 互质的数的个数。

• Example：\varphi(1)=1，因为小于等于 1 的正整数且与 1 互质的数只有 1。

• 当 n 为质数时，显然有 \varphi(n)=n-1，因为除 n 外的其他 n-1 个数均与 n 互质。

Part 2. 性质

欧拉函数是积性函数，即 \varphi(nm)=\varphi(n)\times\varphi(m)。

这里放出几个我会证明的性质：

• 性质 1：若 n=p^k，且 p 为质数，k 为正整数，则 \varphi(n)=p^k-p^{k-1}

证明：显然 n 仅包含 p 这一个质因子，那么 [1,n] 范围内不与 n 互质的数的个数就是 \dfrac{n}{p}=p^{k-1}，则 \varphi(n)=p^k-p^{k-1}，得证。

• 性质 2：由唯一分解定理，设 n=\prod\limits_{i=1}^s p_i^{k_i}，其中 p_i 是质数，则 \varphi(n)=n\times \prod\limits_{i=1}^s \dfrac{p_i-1}{p_i}。

证明：由上文可得 \varphi(p^k)=p^k-p^{k-1}，即 \varphi(p^k)=p^{k-1}\times(p-1)。

因为欧拉函数是积性函数，所以有

得证。

Part 3. 求解

• 对于单个数求解欧拉函数，我们直接利用性质 2 使用分解质因数即可，时间复杂度 O(\sqrt{n})。

代码如下：

int getphi(int x){
    int ans=x;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            ans=ans/i*(i-1);
            while(x%i==0)x/=i;
        }
    }
    if(x>1)ans=ans/x*(x-1);
    return ans;
}

• 对于多个数一起求解则可使用线性筛求解。

方法：因为线性筛可以筛出每个数的最小质因子，设当前的合数为 n，其最小质因子为 p，令 n'=\dfrac{n}{p}，此时要进行分类讨论。

若 n' \bmod p=0，则 n' 包含了 n 的所有因子，有 \varphi(n)=n\times \prod\limits_{i=1}^s \dfrac{p_i-1}{p_i}=p\times n'\times \prod\limits_{i=1}^s \dfrac{p_i-1}{p_i}=p\times \varphi(n')

若 n'\bmod p\neq 0，则有 \varphi(n)=\varphi(p)\times\varphi(n')=(p-1)\times\varphi(n')。

若要求 [1,n] 范围内每个数的欧拉函数，则时间复杂度为 O(n)。

代码：

void getphi(int x){
    is[1]=1;phi[1]=1;
    for(int i=2;i<=x;i++){
        if(!is[i])phi[i]=i-1,p[++cnt]=i;
        for(int j=1;j<=cnt&&i*p[j]<=x;j++){
            is[i*p[j]]=1;
            if(i%p[j]==0){
                phi[i*p[j]]=p[j]*phi[i];
                break;
            }
            else phi[i*p[j]]=(p[j]-1)*phi[i];
        }
    }
}

Part 4. （扩展）欧拉定理

• 欧拉定理的定义：若 \gcd(a,m)=1，则 a^{\varphi(m)}\equiv 1\pmod{m}。

• 扩展欧拉定理定义如下：

证明详见 OI wiki：Link。

板子 Link。