贡献者： int256
定义 1 欧拉函数
欧拉函数 $\varphi(n)$ 表示 $n$ 以内的非零自然数中与 $n$ 互质的数的个数。也可以表示为，
$$\varphi(n) = \sum_{1 \le d \le n, \gcd(d, n) = 1} 1 ~.$$
其中 $\gcd$ 为求最大公约数，故可以用 $\gcd(d, n)=1$ 表示要求 $d$ 与 $n$ 互质。
考察一个数论函数，我们经常按素数——素数幂次——非零自然数的顺序去考察。先探讨前两个的性质。
显然对于任意素数 $p$，其欧拉函数为 $\varphi(p) = p-1$。
对于一个素数幂次 $p^k$，可以想象在 $[1, p^k]$ 内每 $p$ 个数就有一个与 $p^k$ 不互素（有公因子 $p$）。也就是除去所有的 $p$ 的倍数，均与 $p^k$ 互质，故素数幂次的欧拉函数可以表示为 $\varphi(p^k) = p^k \left(1 - (1/p)\right)$。
推论 1 任意非零自然数 $n$ 的欧拉函数
\begin{equation}
\varphi(n) = n \cdot \prod_{i, p_i | n} \left( 1 - \frac1{p_i}\right)~.
\end{equation}
证明：可以利用容斥原理：
不妨设 $n = \prod {p_i^{k_i}}$，$p_i$ 是 $n$ 的各素因子，$k_i$ 是其幂次。则有：
- 不超过 $n$ 的是某个 $p_i$ 的倍数的分别有 $n/p_i$ 个。
- 不超过 $n$ 的是某两 $p_i$ 的倍数的，也即是 $p_i p_j$ 的倍数（$i \neq j$）的，有 $n/(p_i p_j)$ 个。在上面重复计数，需要减去。
- 不超过 $n$ 的是某三 $p_i$ 的倍数的，也即是 $p_i p_j p_k$ 的倍数（$i, j, k$ 互不相等），有 $n/(p_i p_j p_k)$ 个。在上面被减去了，没有计数到，需要加上。
- 依此类推...
- 不超过 $n$ 的是所有 $p_i$ 的倍数的，即 $\prod p_i$ 的，有 $n/(\prod p_i)$ 个。根据 $i$ 的奇偶性决定是要加上或减去。
我们发现这表达式可以将欧拉函数表示为：
$$\varphi(n) = n - \sum(n/p_i) + \sum_{i\le j} (n/(p_i p_j)) \cdots ~, $$
恰好与下面的展开式对应（之后默认的情况下忽略 $p_i | n$ 的条件不写）：
$$\varphi(n) = n \cdot \prod_i \left( 1 - \frac1{p_i}\right)~.$$
这就是计算某任意数的欧拉函数的方法。
1. 积性函数
证明：
回顾积性函数的定义，对于互质的 $n, m$，要求 $\varphi(n m ) = \varphi(n) \varphi(m)$。将 $n$、$m$ 的质因子列出，假设 $n$、$m$ 分别有质因子 $p_i$、$q_i$，则 $nm$ 的所有质因子为 $p_i, q_i$（$p_i \neq q_j, \forall (i, j)$，因为 $n$ 与 $m$ 互质）。从而利用上面的推论 1 ，他们的积的欧拉函数可以表示为，
\begin{equation}
\begin{aligned}
\varphi(n m) &= nm \prod_i \left(1-\frac1{p_i}\right) \prod_i \left(1-\frac1{q_i}\right)\\
&= \left(n \prod_i \left(1 - \frac1{p_i}\right)\right) \left(m \prod_i \left(1 - \frac1{q_i}\right)\right)\\
&= \varphi(n) \varphi(m) ~.
\end{aligned}
\end{equation}
这就完成了证明。
2. 缩系
由欧拉函数的定义，我们可以立刻得知一个推论：
推论 2
$m$ 的缩系的元素个数是 $\varphi(m)$。
定理 2
若 $a_1, a_2, \dots, a_{\varphi(m)}$ 取遍 $m$ 的一个缩系，则对于一个与 $m$ 互质的整数 $k: (k, m) = 1$，则
$k a_1, k a_2, \dots, k a_{\varphi(m)}$ 也取遍 $m$ 的一个缩系。
证明可以直接考虑模仿完全剩余系时的情形，即定理 2 的证明。可以证明 $k a_i$ 之间两两不同余，而由于 $(k, m) = 1$，各 $k a_i$ 必定都与 $m$ 互质，故他们取遍 $m$ 的一个缩系。