Skip to content

欧拉函数

2021-08-20

INFO

若无特殊说明,本章涉及的变量皆为正整数。

定义

n 的欧拉函数为 [1,n] 中与 n 互质的数的个数,记为 φ(n)。特别地,φ(1)=1

性质

质数的欧拉函数

p 为质数,则 φ(p)=p1

p[1,p1] 中的每个数互质。

pk 的欧拉函数

p 为质数,n=pk,则 φ(n)=pkpk1

[1,n] 中,只有 p 的倍数不与 n=pk 互质。

[1,n]p 的倍数有 np=pkp=pk1 个,

φ(n)=npk1=pkpk1

通项公式

nm 个质因子 p1pm,则 φ(n)=ni=1m(11pi)

n 有质因子 p,则 p 的倍数不与 n 互质。

[1,n]p 的倍数有 np 个,则剩下的 nnp=n(11p) 个数不是 p 的倍数。也就是说,这 n 个数中,非 p 的倍数占比为 11p

根据定义,[1,n] 中有 φ(n) 个数不是 p1pm 的倍数(即与 n 互质)。由乘法原理得:

φ(n)=n(11p1)(11p2)(11pm)=ni=1m(11pi)

积性函数

n,m 互质,则 φ(nm)=φ(n)φ(m)

nx 个质因子 p1px

my 个质因子 q1qy

n,m 互质,n,m 的质因子互不相同。

nmx+y 个质因子 p1px,q1qy

φ 函数的通项公式可得:

φ(n)φ(m)=ni=1x(11pi)mi=1y(11qi)=nmi=1x(11pi)i=1y(11qi)=φ(nm)

定理

欧拉定理

a,n 互质,则 aφ(n)1(modn)

C={C1,C2,,Cφ(n)} 为模 n简化剩余系

aC={aC1,aC2,,aCφ(n)},即 C 中的每个元素乘 a

引理 1

剩余系 的定义得:

ij,CiCj(modn)

a,n 互质,由同余的 同乘性 可知:

ij,aCiaCj(modn)

aC 为模 n 的剩余系。

引理 2

a,n 互质,根据 欧几里得算法 有:

gcd(a,n)=gcd(n,amodn)=1

amodn 也与 n 互质。

根据 简化剩余系 的定义可知:

amodnC

简化剩余系满足 乘法封闭 性质,所以:

{amodnCCiC(amodn)CimodnCaCimodnC

aCimodnn 互质,即 aC 中的任意元素模 n 后与 n 互质。

结合引理 1、引理 2 可知 aC 也为 n 的简化剩余系。

显然,C 的所有元素之积和 aC 的所有元素之积模 n 同余,即:

i=1φ(n)Cii=1φ(n)aCi(modn)i=1φ(n)Ciaφ(n)i=1φ(n)Ci(modn)(aφ(n)1)i=1φ(n)Ci0(modn)

C 中的所有元素模 n 后与 n 互质,所以:

i=1φ(n)Ci0(modn)

aφ(n)10(modn),即 aφ(n)1(modn)

费马小定理

p 为质数,则 ap1a(modp)

pa 时,费马小定理显然成立,故只需讨论 pa 的情况。

pa 时,p 是质数 a,p 没有公因数(即 a,p 互质)。根据 欧拉定理 有:

aφ(p)1(modp)

p 为质数,由 性质 可知 φ(p)=p1。代入上式:

ap11(modp)

即证。

扩展欧拉定理

a,n 互质,则对于任意 b,有 ababmodφ(n)(modn)

bmodφ(n)=q,则 b 可以表示为 kφ(n)+q. 代入 ab 得:

ab=akφ(n)+q=(aφ(n))kaq

根据 欧拉定理,当 a,n 互质时,有:

aφ(n)1(modn)

由同余的 同幂性同乘性 可知:

(aφ(n))k1k=1(modn)(aφ(n))kaqaq(modn)abaq(modn)

ababmodφ(n)(modn)

模板

欧拉函数

cpp
int varphi(int n) {
    int ans = n;
    for (int i = 2; i <= sqrt(n); i ++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    }
    if (n > 1)
        ans = ans / n * (n - 1);
    return ans;
}

线性欧拉算法

1n 的欧拉函数。

对质数的 线性筛法 加以改造。

  • i 为质数,则 φ(i)=i1
  • 利用 iprimej 生成合数时,利用 积性函数 性质:
φ(iprimej)=φ(i)φ(primej)

时间复杂度为 O(n)

cpp
const int N = 1e6;
int phi[N];
vector<int> prime;

void varphi(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i ++) {
        if (!phi[i])
            phi[i] = i - 1, prime.push_back(i);
        for (int j = 0; j < prime.size(); j ++) {
            if (i * prime[j] > n) break;
            phi[i * prime[j]] = phi[i] * phi[prime[j]]; // 积性函数
            if (i % prime[j] == 0) break;
        }
    }
}