欧拉函数&欧拉定理

2023-08-05 14:38 由星影流灿发表于 #其他

欧拉函数

互质：对于 $\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 <p_m $ 。

于是就有一个公式：

\[\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。