欧拉函数

定义

$n$ 的欧拉函数记作 $\phi(n)$ ， 表示$1$ ~ $n$ 中与 $n$ 互质的数的个数。

表达式

首先要知道的定理与性质

1 - 积性函数

若 $a$ ， $b$ 互质，则 $\phi(ab) = \phi(a) \; \phi(b)$

2 - 整数的唯一分解定理

一个大于 $1$ 的正整数 $N$ 总可以分解为若干个质因子的乘积，而且这种分解是唯一的。

即 $N=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{k}^{\alpha_{k}}$ 。

推算过程

根据整数的唯一分解定理，

$N=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{k}^{\alpha_{k}}$ 。

根据欧拉函数的积性函数性质，

$\phi(N)= \phi(p_{1}^{\alpha_{1}}) \; \phi(p_{2}^{\alpha_{2}}) \; \cdots \; \phi(p_{k}^{\alpha_{k}})$ （因为 $p^{\alpha}$ 之间互质嘛）。

根据欧拉函数的定义，

$\phi(p^{\alpha})$ 表示 $1$ ~ $p^{\alpha}$ 中与 $p^{\alpha}$ 互质的数的个数，

也就是这 $p^{\alpha}$ 个数中排除掉与 $p^{\alpha}$ 不互质的数

剩下的数的数量。即 $\phi(p^{\alpha})=p^{\alpha}-p^{\alpha-1}=p^{\alpha}(1-\frac{1}{p})$

将这个规律代入到 $\phi(N)$ 中，得

$ \begin{align} \phi(N) &=p_{1}^{\alpha_{1}}(1-\frac{1}{p_{1}}) \; p_{2}^{\alpha_{2}}(1-\frac{1}{p_{2}}) \; \cdots \; p_{k}^{\alpha_{k}}(1-\frac{1}{p_{k}}) \\\\ &=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{k}^{\alpha_{k}} \; (1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}}) \cdots (1-\frac{1}{p_{k}}) \\\\ &=N \; (1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}}) \cdots (1-\frac{1}{p_{k}}) \\\\ &=N \; \prod_{i=1}^{k} (1-\frac{1}{p_{i}}) \end{align} $

性质

性质一

内容

若 $p$ 为质数， $\phi(p) = p - 1$ 。

证明

$1$ ~ $p$ 范围内除了 $p$ 都与 $p$ 互质。

性质二

内容

若 $p \; | \; i$ ， 则 $\phi(ip) = p \times \phi(i)$

证明

$ \begin{align} \phi(ip) &=\phi(p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p^{\alpha} \cdots p_{k}^{\alpha_{k}} \times p) \\\\ &=\phi(p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p^{\alpha+1} \cdots p_{k}^{\alpha_{k}}) \\\\ &=ip \; (1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}}) \cdots (1-\frac{1}{p}) \cdots (1-\frac{1}{p_{k}}) \\\\ &=p \times \phi(i) \end{align} $

性质三

内容

若 $x$ ， $p$ 互质，则 $x^{\phi(p)} \equiv 1 \; (mod \; p)$ 。

首先要知道的定理与性质

1 - 二项式定理

$(x+y)^{n}=\sum\limits_{i=0}^{n} C_{n}^{i} \, x^{i}y^{n-i}$ ，证明略。

2 - 费马小定理

若 $p$ 为质数，则 $a^{p-1} \equiv 1 \; (mod \; p)$ 。

证明：

用数学归纳法证明。

假定 $a^{p-1} \equiv 1 \; (mod \; p)$ 成立，

即 $a^{p} \equiv a \; (mod \; p)$ 。

根据二项式定理，

$(a+1)^{p}=\sum\limits_{i=0}^{p} C_{p}^{i} \, x^{i}y^{p-i}=1+\sum\limits_{i=1}^{p-1}{C_p^{i} \, a^{i}}+a^{p} \equiv a^{p}+1 \equiv a+1 \; (mod \; p)$ 。

在 $a^{p} \equiv a \; (mod \; p)$ 成立的条件下， $(a+1)^{p} \equiv a+1 \; (mod \; p)$ 也成立。

而 $1^p \equiv 1 \; (mod \; p)$ 一定成立，所以定理正确。

证明

$x^{\phi(p)}=x^{p-1} \equiv 1 \; (mod \; p)$ （用到了性质一与费马小定理）。

性质四

内容

$1$ ~ $n$ 中与 $n$ 互质的数的和为 $\frac{n \times \phi(n)}{2}$ 。

证明

根据辗转相减法， $gcd(x,n)=gcd(n-x,n)$ ，

若要 $x$ 与 $n$ 互质（$gcd(x,n)=1$）， $x$ 可取的值有 $\phi(n)$ 个，

而 $x$ 的每个取值都有与之对应的 $n-x$ 也与 $n$ 互质（$gcd(n-x,n)=gcd(x,n)=1$）。

二者相加，结果为 $n$ 。

排除重复的情况（除以二）。

代码

线性求欧拉函数。

void get(int x)
{
    phi[1] = 1;
    for (int i = 2; i <= x; i ++)
    {
        if (!st[i])
        {
            primes[cnt ++] = i;
            phi[i] = i - 1; //性质一
        }
        for (int j = 0; primes[j] * i <= x; j ++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
            {
                phi[primes[j] * i] = primes[j] * phi[i]; //性质二
                break;
            }
            else phi[primes[j] * i] = phi[primes[j]] * phi[i]; //积性函数性质
        }
    }
}