欧拉函数&欧拉定理

欧拉函数

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

热门相关:我的治愈系游戏   豪门情变,渣总裁滚远点!   不科学御兽   豪门情变,渣总裁滚远点!   后福