欧拉函数

互质：对于 $\forall a, b \in \mathbb{N} $， 若 \(a, b\) 的最大公因数为 \(1\) ， 则称 \(a, b\) 互质。

欧拉函数:即 $ \varphi (N)$, 表示从 \(1\) 到 \(N\) 中与 \(N\) 互质的数的个数。

在算术基本定理中， 任何一个大于 \(1\) 的整数都可以唯一分解为有限个质数的乘积， 写作；

(资料图)

\[N = p_1^{c_1}p_2^{c_2} \ldots p_m^{c_m} \]

其中， \(p_i\) 为质数， \(c_i\) 为正整数， 且 $ p_1 < p_2 < \ldots

于是就有一个公式：

\[\varphi(N) = N \cdot \frac{p_1 - 1}{p_1} \cdot \frac{p_2 - 1}{p_2} \cdot \ldots \cdot \frac{p_m - 1}{p_m} = N \cdot \prod_{\text{质数}p|N}^{} (1 - \frac{1}{p})\]

证法一

首先一个数要与 \(N\) 互质的数， 则充要条件是它的质因子都不会在 \(N\) 的质因子当中出现。因此，我们只需要将 \(N\) 分解每个质因子 \(p_i\) ， 再从 \(1 \sim N\) 中去除可以被 \(p_i\) 整除的数，最后剩下的就一定都是与 \(N\) 互质的数了。当我们去除 \(1 \sim N\) 中与被 \(p_1\) 整除的数时，\(1 \sim N\) 中 \(p\) 的倍数 \(p_1, 2p_1, 3p_1, \ldots N / p_1 \cdot p_1\) 这 $ N / p_1 $ 个数都会被去除。则此时 \(N\) 中质因子不包括 \(p_1\) 的数有 $ N - \frac{N}{p_1}$个。同理， 当我们去除 \(1 \sim N\) 中与被 \(p_2\) 整除的数时，也会去除 \(N / p_2\) 个数。但若有数即使 \(p_1\) 也是 \(p_2\) 的倍数, 即 \(p_1 \cdot p_2\) 的倍数，就会被去除 \(2\) 次，因此还要加回来一次。这时 \(1 \sim N\) 中不含有质因子 \(p_1\) 与 \(p_2\) 的数的个数为：

\[N - \frac{N}{p_1} - \frac{N}{p_2} + \frac{N}{p_1p_2} = N * (1 - \frac{1}{p_1} - \frac{1}{p_2} + \frac{1}{p_1p_2}) = N(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\]

依次类推，类似的读者也可以自己试着推一下当去除 \(p_3\) 的倍数的情况，这样一直推下去，就能推出上面的公式。给一个更好理解的方式：设 $ 1 \sim N$ 中的一个整数 \(a\) 能被 \(k\) 个 \(N\) 的质因子整除，于是它的去除次数就是：

\[C_{k}^{1} - C_{k}^{2} + C_{k}^{3} - \ldots + (-1) ^ k - 1 \cdot C_{k}^{k} = 1 \]

上式由二项式定理可得。（别问，我也不会QAQ，初三OIer瑟瑟发抖）

这就保证了每个质因子包含了 \(N\) 的质因子的数有且只会被去除一次。

这种思想就叫做容斥原理。长这样：

应该都能看懂吧 ，看懂的扣1，看不懂的扣眼珠子，我才不会说我是懒

证法二：

欧拉函数有一个性质，即它是积性函数。

积性函数：对于任意互质的整数 \(a\) 和 \(b\) 有性质\(f(ab)=f(a)\cdot f(b)\)的数论函数。

证明如下：

设 \(a\) 的所有质因子为\(\left \{p_1, p_2, \ldots, p_{m1} \right \}\) , \(b\) 的所有质因子为 \(\left\{q_1, q_2, \ldots, q_{m2} \right\}\), \(ab\) 的所有质因子为\(\left\{r_1, r_2, \ldots, r_{m3} \right\}\) 。则：

\[\varphi(a) = a \cdot \frac{p_1 - 1}{p_1} \cdot \frac{p_2 - 1}{p_2} \cdot \ldots \cdot \frac{p_{m1} - 1}{p_{m1}}\]\[\varphi(b) = b \cdot \frac{q_1 - 1}{q_1} \cdot \frac{q_2 - 1}{q_2} \cdot \ldots \cdot \frac{q_{m2} - 1}{q_{m2}}\]\[\begin{aligned}\varphi(a) \cdot \varphi(b)&= a \cdot \frac{p_1 - 1}{p_1} \cdot \frac{p_2 - 1}{p_2} \cdot \ldots \cdot \frac{p_{m1} - 1}{p_{m1}} \cdot b \cdot \frac{q_1 - 1}{q_1} \cdot \frac{q_2 - 1}{q_2} \cdot \ldots \cdot \frac{q_{m2} - 1}{q_{m2}} \\&=ab \cdot \frac{p_1 - 1}{p_1} \cdot \frac{p_2 - 1}{p_2} \cdot \ldots \cdot \frac{p_{m1} - 1}{p_{m1}}\cdot \frac{q_1 - 1}{q_1} \cdot \frac{q_2 - 1}{q_2} \cdot \ldots \cdot \frac{q_{m2} - 1}{q_{m2}}\end{aligned}\]\[\varphi(ab) = ab \cdot \frac{r_1 - 1}{r_1} \cdot \frac{r_2 - 1}{r_2} \cdot \ldots \cdot \frac{r_{m3} - 1}{r_{m3}}\]

因为 \(a\) 与 \(b\) 互质，所以对于任意的 \(a\) 的质因子 \(p_i\), \(b\) 的质因子\(q_j\), 都有 \(p_i \ne q_j\)。因此， \(ab\)的所有质因子 \(\left \{r_1, r_2, \ldots, r_{m3} \right \} = \left \{p_1, p_2, \ldots, p_{m1} \right \} + \left \{q_1, q_2, \ldots, q_{m2} \right \}\) 。

因此，

\[\frac{p_1 - 1}{p_1} \cdot \frac{p_2 - 1}{p_2} \cdot \ldots \cdot \frac{p_{m1} - 1}{p_{m1}}\cdot \frac{q_1 - 1}{q_1} \cdot \frac{q_2 - 1}{q_2} \cdot \ldots \cdot \frac{q_{m2} - 1}{q_{m2}} = \frac{r_1 - 1}{r_1} \cdot \frac{r_2 - 1}{r_2} \cdot \ldots \cdot \frac{r_{m3} - 1}{r_{m3}}\]

即：

\[\varphi(ab) = \varphi(a) \cdot \varphi(b)\]

证毕。

由算术基本定理，

\[N = p_1^{c_1}p_2^{c_2} \ldots p_m^{c_m} \]

对于每项 \(\varphi(p_i^{c_i})\)， 从定义出发，表示从\(1 \sim p_1^{c_1}\) 之间所有与 \(p_1^{c_1}\) 互质的数的个数。因为 \(p_1\) 为质数，所以只有 \(p_1\) 的倍数才是不与 \(p_1 ^ {c_1}\) 互质的数。因此\(\varphi(p_i^{c_i}) = p_i^{c_i} - p_i^{c_i - 1}\)。

于是

\[\begin{aligned}N &= (p_1^{c_1} - p_1^{c_1 - 1})(p_2^{c_2} - p_2^{c_2 - 1}) \ldots(p_m^{c_m} - p_m^{c_m - 1}) \\&=p_1^{c_1}(1- \frac{1}{p_1})p_2^{c_2}(1 - \frac{1}{p_2}) \ldots p_m^{c_m}(1 - \frac{1}{p_m}) \\&=p_1^{c_1}p_2^{c_2} \ldots p_m^{c_m}\prod_{i = 1}^{m}(1 - \frac{1}{p_i}) \\&=N \cdot \prod_{\text{质数}p|N}^{}(1 - \frac{1}{p}) \end{aligned}\]

欧拉定理

欧拉定理：若 \(\gcd(a, m) = 1\) ， 则 $ a ^ {\varphi(m)} \equiv 1 \pmod{m}$

这里就需要一丢丢数论基础，让我来稍做补充（日后另开一篇）：

• 剩余系：对于任意正整数 \(m\) ，一个数除以 \(m\) 所得的余数只能是 $ 0, 1, 2, \ldots, m - 1 $ 中的某一个，因此可以将整数分为 \(m\) 个类。每个类叫做剩余类。从中任选任意多个类，从这些类中各取一个数，构成一个集合，就将这个集合称为模 \(m\) 的剩余系。
• 完全剩余系（完系）：从模 \(m\) 的 \(m\) 个类中，每类各取 \(1\) 个数所构成的集合就算模 \(m\) 的一个完全剩余系，简称为模 \(m\) 的完系。
• 简化剩余系（缩系）：如果一个模 \(m\) 的剩余类中存在一个与 \(m\) 互素的剩余，该类叫做简化剩余类；在模 \(m\) 的所有不同简化剩余类中，从每个类任取一个数组成的整数的集合，叫做模 \(m\) 的一个简化剩余系。容易得出， 模 \(m\) 共有 \(\varphi(m)\) 个简化剩余类。

证明：

设 \(r_1, r_2, \ldots, r_{\varphi(m)}\) 为模 \(m\) 意义下的一个简化剩余系， 即\(r_1, r_2, \ldots, r_{\varphi(m)}\)之前互不相同且都与 \(m\) 互为质数， 那么，对于任意 \(r_i, r_j(i \ne j)\), 与 \(a\) 的乘积 \(ar_i, ar_j\) 不相等, 且仍然与 \(m\) 互质（注意， \(a\) 与 \(m\) 互质， 我就因为没注意到这个懵逼了好久QAQ)，因此， \(ar_1, ar_2, \ldots , ar_{\varphi(m)}\)也是模 \(m\) 意义下的一个简化剩余系，则

\[\begin{aligned}r_1r_2 \ldots r_{\varphi(m)} &\equiv ar_1ar_2 \ldots ar_{\varphi(m)}\\&\equiv a^{\varphi(m)}(r_1r_2\ldots r_m) \pmod{m}\end{aligned}\]

约去\((r_1r_2\ldots r_m)\), 得

\[1 \equiv a ^ {\varphi(m)} \pmod{m}\]

证毕。

同时，我们还可以用欧拉定理推出费马小定理：

费马小定理：若 \(p\) 为素数， \(\gcd(a, p) = 1\), 则 $a^{p - 1} \equiv 1 \pmod{p} $

当 \(p\) 为素数时，很显然， \(\varphi(p) = p - 1\)， 因此就有：

\[a^{\varphi(p)} \equiv 1 \pmod{p}\]

就变成了欧拉定理！

参考书籍及网站：《算法竞赛进阶指南》,小蓝本初中卷, OI Wiki, AcWing。

标签：