贡献者： 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$ 的一个缩系。
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。