欧拉函数

· · 个人记录

欧拉函数

定义：

在 1 \sim N 中与 N 互质的数的个数被称为欧拉函数 ，记为 \varphi (N)

若正整数 N 被唯一分解成 N=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m} ，则

\varphi (N)=N*\frac{p_1-1}{p_1}*\frac{p_2-1}{p_2}* \cdots *\frac{p_m-1}{p_m}=N*\prod\limits_{i=1}^m (1-\frac{1}{p_i})

证明：

设 p,q 为 N 的质因子 ，显然 1 \sim N 中 p 的倍数共有 N/p 个 , q 的倍数共有 N/q 个 ，如果我们去掉这 N/p+N/q 个数 ，那么 p*q 的倍数就被我们减了两次 ，根据容斥原理 ，得到 1 \sim N 中不含质因子 p,q 的数的个数为：

N-\frac{N}{p}-\frac{N}{q}+\frac{N}{p*q}=N*(1-\frac{1}{p}-\frac{1}{q}+\frac{1}{p*q})=N(1-\frac{1}{p})(1-\frac{1}{q})

对 N 所有的质因子使用容斥原理 ，即可得到 1 \sim N 中不含任何 N 的质因子的数的个数 ，即与 N 互质的数的个数 ，即为 \varphi (N)

Q.E.D

性质：

性质 1.

\forall \ n > 1$ ，$1 \sim n$ 中与 $n$ 互质的所有数的**和**为 $\varphi (n)*n/2

证明： 因为 gcd(n,x)=gcd(n,n-x) ，所以与 n 不互质的数 x,n-x 总是成对出现 ，显然它们的平均值为 n/2 ，故与 n 互质的数的平均数也是 n/2 ，性质 1 得证 ， 顺便还可以得到 \forall \ n>2 ，\varphi (n) 为偶数

性质 2.

欧拉函数为积性函数 ，即当 a,b 互质时 ，\varphi (ab)=\varphi (a)\varphi (b)

证明： 对 a,b 分别分解质因数 ，再根据欧拉函数的计算式 ，直接可得性质 2

性质 3.

若质数 p \mid n ，且 p^2 \mid n ，则 \varphi (n)=\varphi (n/p)*p

证明： 若质数 p \mid n ，且 p^2 \mid n ，则 n,n/p 包含相同的质因子 ，只有 p 的指数不同 ，根据欧拉函数的计算式 ，得到

\varphi (n)=n*\prod\limits_{i=1}^m (1-\frac{1}{p_i})\ \ \ \varphi (n/p)=n/p*\prod\limits_{i=1}^m (1-\frac{1}{p_i})\ \ \ \varphi (n)=\varphi (n/p)*p\ \ \

性质 4.

若质数 p \mid n ，但 p^2 \nmid n ，则 \varphi (n)=\varphi (n/p)*(p-1)

证明： 若质数 p \mid n ，但 p^2 \nmid n ，则 p,n/p 互质 ，因为欧拉函数是积性函数 ，得到

\varphi (n)=\varphi (n/p*p)=\varphi (n/p)*\varphi (p)

因为 p 为质数 ，故 \varphi (p)=p-1 ，所以

\varphi (n)=\varphi (n/p)*\varphi (p)=\varphi (n/p)*(p-1)

性质 5.

若 p 为质数 ，则 \varphi (p^k)=p^k-p^{k-1}

证明： 根据性质 3 ，得到

\varphi (p^k)=\varphi (p^{\ k-1}*p)=\varphi (p^{\ k-1})*p=\varphi (p^{\ k-2})*p^2=\cdots=\varphi (p)*p^{\ k-1}

因为 p 为质数 ，故 \varphi (p)=p-1 ，所以

\varphi (p^k)=p^{\ k-1}*\varphi (p)=p^{\ k-1}*(p-1)=p^k-p^{k-1}

性质 6.

\sum_{d \mid n} \varphi(d)=n

证明： 设 f(n)=\sum_{d \mid n} \varphi(d) ，根据乘法分配律和 \varphi 是积性函数 ，可以得到：若 n,m 互质 ，则

f(nm)=\sum_{d \mid {nm}} \varphi(d)=\left(\sum_{d \mid {n}} \varphi(d)\right)*\left(\sum_{d \mid {m}} \varphi(d)\right)=f(n)*f(m)

故 f 也是积性函数 ，因此对 n 进行质因子分解后 ，对于单一质因子 p ，有

f(p^c)=\sum_{d \mid {p^c}} \varphi(d)=\varphi(p^c)+\varphi(p^{c-1})+\cdots+\varphi(p)+\varphi(1)

再根据性质 5 ，得到

f(p^c)=\varphi(p^c)+\varphi(p^{c-1})+\cdots+\varphi(p)+\varphi(1)=p^{c}-p^{c-1}+p^{c-1}-p^{c-2}+\cdots+p-1+1=p^c f(n)=\sum_{d \mid n} \varphi(d)=\prod\limits_{i=1}^m f(p_i^{c_i})=\prod\limits_{i=1}^m p_i^{c_i}=n

性质 7.

欧拉定理： 若正整数 a,n 互质 ，则 a^{\varphi(n)}\equiv 1 \pmod n

证明： 设 n 的简化剩余系为 \{\overline{a_1},\overline{a_2},\cdots,\overline{a_{\varphi(n)}} \} ，则对于 \forall \ a_i \ne a_j ，aa_i,aa_j 一定代表不同的剩余系

假设aa_i,aa_j 代表同样的剩余系 ，则 a*a_i\equiv {a_k} \pmod n\ ,\ a*a_j\equiv {a_k} \pmod n ，所以 a*a_i\equiv {a*a_j} \pmod n ，因为 a,n 互质 ，两边同除 a 得 a_i\equiv {a_j} \pmod n ，故 a_i=a_j ，矛盾

又因为简化剩余系关于模 n 乘法封闭 ，故 aa_i 一定也在 n 的简化剩余系中 ，所以集合 \{\overline{a_1},\overline{a_2},\cdots,\overline{a_{\varphi(n)}} \} 与集合 \{\overline{aa_1},\overline{aa_2},\cdots,\overline{aa_{\varphi(n)}} \} 都能表示 n 的简化剩余系 ， 所以

a^{\varphi(n)}a_1a_2 \cdots a_{\varphi(n)}\equiv {(aa_1)(aa_2)\cdots (aa_{\varphi(n)})}\equiv a_1a_2 \cdots a_{\varphi(n)}\pmod n

显然 a_1a_2 \cdots a_{\varphi(n)} 与 n 互质 ，上式两边同除 a_1a_2 \cdots a_{\varphi(n)} 即可得到 a^{\varphi(n)}\equiv 1 \pmod n

特别地 ，当 n 为质数时 ，\varphi(n)=n-1 ，故 a^{n-1}\equiv 1 \pmod n ，即费马小定理

性质 8.

若正整数 a,n 互质 ，则对于任意正整数 b ，有 a^b\equiv a^{b \% \varphi(n)} \pmod n

证明： 设 b=k*\varphi(n)+r ，其中 r=b \% \varphi(n) ，根据欧拉定理可得

a^b\equiv a^{k*\varphi(n)+r} \equiv (a^{\varphi(n)})^k *a^r\equiv 1^k+a^r \equiv a^r \equiv a^{b \% \varphi(n)} \pmod n

性质 9.

当 a,n 不保证互质且 b>\varphi(n) 时，有 a^b\equiv a^{b \% \varphi(n)+\varphi(n)} \pmod n

证明： 不会

性质 10.

若正整数 a,n 互质 ，则满足 a^x \equiv 1 \pmod n 的最小正整数解 x_0 是 \varphi(n) 的约数

证明： 假设满足 a^x \equiv 1 \pmod n 的最小正整数解 x_0 不是 \varphi(n) 的约数 ，设 \varphi(n)=kx_0+r \ \ (0<r<x_0)

根据欧拉定理可得

a^{\varphi(n)}\equiv a^{kx_0+r}\equiv 1 \pmod n

又因为

a^{x_0} \equiv 1 \pmod n a^{kx_0} \equiv 1 \pmod n

所以

a^{\varphi(n)}/a^{kx_0}\equiv a^{kx_0+r}/a^{kx_0}\equiv a^r\equiv 1 \pmod n

而 r<x_0 ，且满足 a^{r} \equiv 1 \pmod n ，因此 x_0 不是满足 a^x \equiv 1 \pmod n 的最小正整数解 ，矛盾 ，故性质 10 得证

求欧拉函数：

求法1：分解质因数

根据欧拉函数的计算式 ，我们只需要分解质因数就可以计算欧拉函数了

inline int phi(int x){
    int ans=x;
    for(int i=2;i*i<=x;i++)
        if(x%i==0){//此时i显然是质数 
            ans=ans/i*(i-1);
            while(x%i==0) x/=i;
        }
    if(x>1) ans=ans/x*(x-1);//特判x最终还是质数 
    return ans;
}

求法2：欧拉筛

根据性质 3,4 ，我们可以通过欧拉筛来求 \varphi ，从而得到 \forall \ 1\le i \le n ， \varphi(i) 的值

    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!v[i]) v[i]=1, p[++tot]=i, phi[i]=i-1;
        for(int j=1;j<=tot && p[j]*i<=n;j++){
            v[p[j]*i]=1;
            phi[p[j]*i]=phi[i]*(p[j]-(i%p[j]!=0));
            if(i%p[j]==0) break;
        }
    }