欧拉函数

欧拉函数

\(\varphi(n)\)表示小于等于n的与n互质的数的个数

\(\varphi(n)=\sum_{k<=n}[gdc(k,n)=1]\)

性质

1. \(\varphi(n)\)是积性函数

2. \(n=\sum_{d|n}{\varphi(d)}\)

3. 若\(n=p^k\)，\(p\)是质数，则\(\varphi(n)=p^k-p^{k-1}\)

证明：

有\(n/p=p^{k-1}\)个数和n不互质，故与其互质的有\(n-p^{k-1}=p^k-p^{k-1}\)个

4. 若\(n=\prod_{i=1}^{s} p_{i}^{k_{i}}\)，则\(\varphi(n)=n \prod_{i=1}^{s}\left(1-\frac{1}{p_{i}}\right)\)

\[ \begin{aligned} \varphi(n) & =\prod_{i=1}^{s} \varphi\left(p_{i}^{k_{i}}\right) \\ & =\prod_{i=1}^{s}\left(p_{i}-1\right) \times {p_{i}^{k_{i-1}}} \\ & =\prod_{i=1}^{s} p_{i}^{k_{i}} \times\left(1-\frac{1}{p_{i}}\right) \\ & =n \prod_{i=1}^{s}\left(1-\frac{1}{p_{i}}\right) \end{aligned} \]

欧拉函数的代码实现

int euler_phi(int n){
    int ret=n;
    for(int i=2;i*i<=n;++i){
        if(n%i==0){
            ret=ret/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ret=ret/n*(n-1);
    return ret;
}

欧拉定理

若\((a,m)=1\)，则\(a^{\varphi(m)}\equiv1(mod\,m)\)

证明见欧拉定理证明。