欧拉函数
互质：对于 $\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\) 的质因子整除，于是它的去除次数就是：
上式由二项式定理可得。（别问，我也不会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\) 意义下的一个简化剩余系，则
约去\((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。
标签：frac,函数,cdot,定理,varphi,m1,互质,ldots,欧拉 From： https://www.cnblogs.com/yduck/p/17607470.html