欧拉函数

注意:若无特殊说明,本章涉及的变量皆为正整数.

定义 #

$n$ 的欧拉函数为 $[1,n]$ 中与 $n$ 互质的数的个数,记为 $\varphi(n)$. 特别地,$\varphi(1)=1$.

性质 #

质数的欧拉函数 #

$p$ 为质数,则 $\varphi(p)=p-1$.

$p$ 与 $[1,p-1]$ 中的每个数互质.

$p^k$ 的欧拉函数 #

$p$ 为质数,$n=p^k$,则 $\varphi(n)=p^k-p^{k-1}$.

在 $[1,n]$ 中,只有 $p$ 的倍数不与 $n=p^k$ 互质.

$∵\;[1,n]$ 中 $p$ 的倍数有 $\dfrac{n}{p}=\dfrac{p^k}{p}=p^{k-1}$ 个,

$∴\varphi(n)=n-p^{k-1}=p^k-p^{k-1}$.

通项公式 #

$n$ 有 $m$ 个质因子 $p_1∼p_m$,则 $\varphi(n)=n\prod_{i=1}^{m}(1-\frac{1}{p_i})$.

若 $n$ 有质因子 $p$,则 $p$ 的倍数不与 $n$ 互质.

$[1,n]$ 中 $p$ 的倍数有 $\cfrac{n}{p}$ 个,则剩下的 $n-\cfrac{n}{p}=n\cdot(1-\cfrac{1}{p})$ 个数不是 $p$ 的倍数. 也就是说,这 $n$ 个数中,非 $p$ 的倍数占比为 $1-\cfrac{1}{p}$.

根据定义,$[1,n]$ 中有 $\varphi(n)$ 个数不是 $p_1∼p_m$ 的倍数(即与 $n$ 互质). 由乘法原理得:

$$\varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m})=n\prod_{i=1}^{m}(1-\frac{1}{p_i})$$

积性函数 #

$n,m$ 互质,则 $\varphi(nm)=\varphi(n)\cdot \varphi(m)$.

设 $n$ 有 $x$ 个质因子 $p_1\sim p_x$,

设 $m$ 有 $y$ 个质因子 $q_1\sim q_y$,

$∵n,m$ 互质,$∴n,m$ 的质因子互不相同.

$∴nm$ 有 $x+y$ 个质因子 $p_1\sim p_x,q_1\sim q_y$.

由 $\varphi$ 函数的通项公式可得:

$$\begin{aligned} \varphi(n)\cdot \varphi(m)&=(n\prod_{i=1}^{x}(1-\frac{1}{p_i}))\cdot (m\prod_{i=1}^{y}(1-\frac{1}{q_i}))\\ &=nm\prod_{i=1}^{x}(1-\frac{1}{p_i})\prod_{i=1}^{y}(1-\frac{1}{q_i})\\ &=\varphi(nm) \end{aligned}$$

即证.

定理 #

欧拉定理 #

若 $a,n$ 互质,则 $a^{ \varphi(n)}≡1\pmod{n}$.

设 $C=\{C_1,C_2,\cdots,C_{\varphi(n)}\}$ 为模 $n$ 的 简化剩余系.

设 $aC=\{aC_1,aC_2,\cdots,aC_{\varphi(n)}\}$,即 $C$ 中的每个元素乘 $a$.

引理 1

href="/docs/NOI/Math/mod/#%e5%89%a9%e4%bd%99%e7%b3%bb"

剩余系 的定义得:

$$C_i\not≡C_j \ (\bmod \ n)(i\not=j)$$

$∵a,n$ 互质,由同余的 href="/docs/NOI/Math/mod/#%e6%80%a7%e8%b4%a8"

同乘性 可知:

$$aC_i\not≡aC_j \ (\bmod \ n)(i\not=j)$$

$∴aC$ 为模 $n$ 的剩余系.

引理 2

$∵a,n$ 互质,根据 href="/docs/NOI/Math/mod/gcd/"

欧几里得算法 有:

$$gcd(a,n)=gcd(n,a \bmod n)=1$$

$∴a \bmod n$ 也与 $n$ 互质. 根据 href="/docs/NOI/Math/mod/#%e7%ae%80%e5%8c%96%e5%89%a9%e4%bd%99%e7%b3%bb"

简化剩余系 的定义可知:

$$a \bmod n\in C$$

$∵\;$简化剩余系满足 href="/docs/NOI/Math/mod/#%e4%b9%98%e6%b3%95%e5%b0%81%e9%97%ad"

乘法封闭 性质,所以:

$$\begin{cases} a \bmod n\in C \\ C_i\in C \end{cases} \eq(a \bmod n)\cdot C_i \bmod n\in C \eq aC_i \bmod n\in C$$

$∴aC_i \bmod n$ 与 $n$ 互质,即 $aC$ 中的任意元素模 $n$ 后与 $n$ 互质.

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

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

$$\prod_{i=1}^{\varphi(n)}C_i≡\prod_{i=1}^{\varphi(n)}aC_i \ (\bmod \ n)$$

$$\prod_{i=1}^{\varphi(n)}C_i≡a^{\varphi(n)}\cdot \prod_{i=1}^{\varphi(n)}C_i \ (\bmod \ n)$$

$$(a^{\varphi(n)}-1)\prod_{i=1}^{\varphi(n)}C_i≡0 \ (\bmod \ n)$$

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

$$\prod_{i=1}^{\varphi(n)}C_i\not≡0 \ (\bmod \ n)$$

$∴a^{\varphi(n)}-1≡0\pmod{n}$,即 $a^{\varphi(n)}≡1\pmod{n}$.

费马小定理 #

若 $p$ 为质数,则 $a^{p-1}≡a\pmod{p}$.

当 $p\mid a$ 时,费马小定理显然成立,故只需讨论 $p\nmid a$ 的情况.

当 $p\nmid a$ 时,$∵p$ 是质数 $∴a,p$ 没有公因数(即 $a,p$ 互质). 根据 欧拉定理 有:

$$a^{ \varphi(p)}≡1 \ (\bmod \ p)$$

$∵p$ 为质数,由 性质 可知 $\varphi(p)=p-1$. 代入上式:

$$a^{ p-1}≡1 \ (\bmod \ p)$$

即证.

扩展欧拉定理 #

若 $a,n$ 互质,则对于任意 $b$,有 $a^b≡a^{b \bmod \varphi(n)}\pmod{n}$.

设 $b \bmod \varphi(n)=q$,则 $b$ 可以表示为 $k\cdot \varphi(n)+q$. 代入 $a^b$ 得:

$$a^b=a^{k\cdot \varphi(n)+q}=\big(a^{\varphi(n)}\big)^k\cdot a^q$$

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

$$a^{\varphi(n)}≡1 \ (\bmod \ n)$$

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

$$\big(a^{\varphi(n)}\big)^k≡1^k=1 \ (\bmod \ n)$$

$$\big(a^{\varphi(n)}\big)^k\cdot a^q≡a^q \ (\bmod \ n)$$

$$a^b≡a^q \ (\bmod \ n)$$

即 $a^b≡a^{b \bmod \varphi(n)}\pmod{n}$.

模板 #

欧拉函数 #

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;
}

线性欧拉算法 #

求 $1\sim n$ 的欧拉函数.

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

  • 若 $i$ 为质数,则 $\varphi(i)=i-1$.

  • 利用 $i$ 和 $prime_j$ 生成合数时,利用 积性函数 这一性质:

$$\varphi(i\cdot prime_j)=\varphi(i)\cdot\varphi(prime_j)$$

时间复杂度为 $O(n)$.

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;
        }
    }
}