欧拉定理
- 欧拉定理
- 前置芝士
- 1、唯一质数分解定理（Unique factorisation theorem）
- 2、互质（Coprime）、最大公因数（GCD）和最小公倍数（LCM）
- 3、同余关系（Congruence relations）
- 4、同余类(Residue class)、完全剩余系(Complete residue system)、缩剩余系(Reduced residue system)
- 4.欧拉函数(Euler's totient function)
- 正文
- 欧拉定理
- 前置芝士
欧拉定理
本文章大部分摘抄自这里
前置芝士
1、唯一质数分解定理（Unique factorisation theorem）
任意一个正整数 n > 1 都可以唯一的分解为质数的乘积
\[n = 2^{e_1} \times 3^{e_2} \times 5^{e_3} \times ··· = \prod_{i=1}^N p^{e_k}_k \]其中 \(e_1 , e_2 , ··· \in \mathbb{N}\) , 我们称这个分解为 \(n\) 的标准分解
2、互质（Coprime）、最大公因数（GCD）和最小公倍数（LCM）
对于整数 \(a, b\) 我们记 \(\gcd(a. b)\) 和 \(\rm {lcm} (a, b)\) 为 \(a, b\) 的最大公因数和最小公倍数，有时候我们会直接把他们简写为 \((a, b)\) 和 \([a, b]\) 。如果 \(gcd(a, b)\) ，我们称 \(a, b\) 互质，也就是说他们没有任何共同的质因数。
它有几个基本的性质，对于正整数\(a, b, n\)
- \(\gcd(a, b) = \gcd(a \pm b, b)\)
- \(\gcd(na, nb) = n\gcd(a , b)\)
- \(\gcd(a, b) = \Large \frac{a·b}{\rm{lcm}(a, b)}\)
- 斐蜀定理：存在整数 $x, y $使得 \(\gcd(a, b) = ax + by\)
3、同余关系（Congruence relations）
整数 \(a\) 和 \(b\) 除以 \(n\) 的余数相同，则称 \(a, b\) 模 \(n\) 同余，计作
\[a \equiv b (\!\!\!\!\!\!\mod n) \]如果对于整数 \(a_1, a_2, b_1, b_2\) 有
\[a_1 \equiv b_1(\!\!\!\!\!\!\mod n) \]\[a_2 \equiv b_2(\!\!\!\!\!\!\mod n) \]那么可以把它们相加或相减
\[a_1 \pm a_2 \equiv b_1 \pm b_2(\!\!\!\!\!\!\mod n) \]也可以把它们相乘
\[a_1 a_2 \equiv b_1 b_2(\!\!\!\!\!\!\mod n) \]通过这两条性质，我们容易知道，如果 \(a \equiv b(\!\!\!\!\mod n)\) 那么
\[P(a) \equiv P(b)\quad(\!\!\!\!\!\!\mod n) \]对于任意整系数多项式 \(P(x)\) 都成立
这里需要注意一点的是，如果整数 \(a, b, c\) 满足
\[ac \equiv bc(\!\!\!\!\!\!\mod n) \]那么只有当 \(n, c\) 互质时才可以把两边的 \(c\) 直接约掉， 得到 \(a \equiv b (\!\!\!\!\mod n)\) 更一般的
\[a \equiv b (\!\!\!\!\!\!\mod \frac{n}{\gcd (n, c)}) \]4、同余类(Residue class)、完全剩余系(Complete residue system)、缩剩余系(Reduced residue system)
通过一个整数模 \(n\) 的余数，我们可以把所有整数分为 \(n\) 类，记
\[\bar{r}_n = \{ m \in \mathbb{Z} \mid mn + r\} \]为模 \(n\) 余 \(r\) 的同余类(也叫剩余类)举个例子
\[\bar{4}_10 \{ ···,-16, -6, 4, 14, 24,··· \} \]是模\(10\)余\(4\)的同余类 (即余数都是\(4\)，对于负数先\(+mod\)在\(\%mod\)）
从 \(\bar{0}_n, \bar{1}_n, \bar{2}_n, ..., \overline{(n-1)}_n\) 中各挑出一个数就组成了一个模 \(n\) 的完全剩余系（完系） \(R_n\)
\[R_n = \{ r_0, r_1, r_2 ···,r_{n - 1} \} \]其中$r_0 \in \overline{0_n}, r_1 \in \overline{1_n}, r_2 \in \overline{2_n},···, r_{n-1} \in \overline{(n-1)_n} $
换言之，\(n\) 个模 \(n\) 互相不同余的整数组成一个模 \(n\) 的完全剩余系
我们称\(R_n = \{ 0, 1, ···, n - 1 \}\) 为模 \(n\) 的最小非负完全剩余系（最小非负完系）
取一个模 \(n\) 的完全剩余系 \(R_n\) ,取出里面所有和 \(n\) 互质的数，这些数组成一个模 \(n\) 的缩剩余系（缩系），记为 $ \large \Phi_n$
\[\Large\Phi_n = \{ c_1, c_2, ···, c_{\varphi(n)} \} \]其中 \(\varphi(n)\) 是前面提到的欧拉函数，代表 [小于 \(n\) 的正整数中和 $ n$ 互质的数] 的个数
注意，因为 \(\gcd(c_i, n) = \gcd (c_i + n, n) = 1\), 每一个模 \(n\) 的缩剩余系有相同数量的元素（缩剩余系中的每一个数所属的同余类是确定的，所以总有确定的 \(\varphi(n)\) 个同余类）
如果缩剩余系 \(\Phi_n = \{ c_1, c_2, ···, c_{\varphi(n)}\}\) 满足 \(1 \leqslant c_1, c_2, ···，c_{\varphi(n)} \leqslant n - 1\), 那么称其为模 \(n\) 的最小正缩剩余系（最小正缩系）。
4.欧拉函数(Euler's totient function)
对于正整数 \(n\) , \(\varphi(n)\) 代表 [小于 \(n\) 的正整数中和 \(n\) 互质的数] 的个数，这个函数被称作欧拉函数；
欧拉还告诉我们：
\[\frac{\varphi(n)}{n} = \prod_{p \mid n} \large(1 - \frac{1}{p}) \]其中 \(p\) 取到 \(n\) 的所有质因数
所以我们可以很方便的计算一个正整数欧拉函数的值，比如
\[\varphi(1926) = \varphi(2 \times 3^2 \times 107) = 1926(1 - \frac{1}{2})(1 - \frac{1}{3})(1 - \frac{1}{107}) = 636 \]欧拉函数还有一些非常有用的性质:
- 如果正整数 \(n >2\) 那么 \(\varphi(n)\)
- 如果 \(n \mid N\) ,那么 \(\varphi(n) \mid \varphi(N)\)
- 对于正整数 \(a, n\) 有 \(n \mid \varphi(a^n - 1)\)
- 对于正整数 \(m ,n\) 有 \(\varphi(mn) = \varphi(m)\varphi(n)\Large\frac{\gcd(m,n)}{\varphi(\gcd(m,n))}\)
- 特别地，如果 \(m, n\) 互质，那么 \(\varphi(mn) = \varphi(m)\varphi(n)\)
- 对于正整数 \(n\) 有 \(\sum_{d \mid n} \varphi(d) = n\)
- 对于正整数 \(n\) 有 \(\sum_{1 \leqslant k \leqslant n, \gcd(k,n) = 1} \frac{k}{n} = \frac{\varphi(n)}{2}\)
正文
欧拉定理
如果正整数 \(n\) 和整数 \(a\) 互质，那么就有
\[a^{\varphi(n)} \equiv 1 \pmod n \]其中 \(\varphi(n)\) 是欧拉函数
以下是证明：
考虑\(n\)的最小正缩系
\[\Phi_n = \{ c_1, c_2, ···c_{\varphi(n)}\} \]已知 \(\gcd (a, n) = 1\) 我们在 \(\Phi_n\) 的每一个元素前面都乘一个 \(a\)
\[a \Phi_n = \{ ac_1, ac_2, ···, ac_{\varphi(n)} \} \]利用反证法可以证明 \(a\Phi_n\) 也是一个模 \(n\) 的缩系（其元素的同余类的顺序有可能会改变，但这并没有任何影响）， 假设
\[ac_i \equiv ac_j \pmod n \]其中 \(i \ne j\) ,因为 \(a, n\) 互质可以将两边消去 \(a\), 那么就得到
\[c_i \equiv c_j \pmod n \]这是不可能的，因为 \(\Phi_n\) 中的互相模 \(n\) 不同余，出现矛盾了！
接下来的思路就比较清晰了，因为 \(\Phi_n\) 和 \(a\Phi_n\) 都是模 \(n\) 的缩系
\[\prod^{\varphi(n)}_{i = 1}c_i \equiv \prod^{\varphi(n)}_{i = 1}ac_i = a^{\varphi(n)} \prod^{\varphi(n)}_{i = 1}c_i \pmod n \]显然
\[\gcd(n, \prod^{\varphi(n)}_{i = 1} c_i) = 1 \]所以可以两边消去它
\[a^{\varphi(n)} \equiv 1 \pmod n \]然后我们就证毕了，是不是意外的简单？
另外，如果我们让 \(n = q\) 是一个质数，我们就可以从欧拉定理推出费马小定理（Feramt's little theorem）
如果 \(p\) 是质数，那么 \(p \mid n^p - n\) 对于任意整数 \(n\) 都成立
当然，费马小定理也可以用归纳法证明，假设 \(p \mid n^p - n\) 那么
\[(n ＋ 1) ^ p - (n + 1) = \sum^{p - 1}_{r = 1} \dbinom{p}{r} n^r + n ^ p - n \]当 \(1 \leqslant r \leqslant p - 1\) 时，二项次系数 \(\dbinom{p}{r} = \Large\frac{p!}{(p -r)!r!}\) 的分子中有 \(p\) ，分母中每一个乘子都不能整除 \(p\) （因为 \(p\) 是质数），所以 \(p\) 能够整除 \(\dbinom{p}{r}\), 进而得到 \(p \mid (n + 1)^p - (n + 1)\)。当 \(n = 0\) 时显然成立，所以定理成立
接下来我们看看如何证明
\[\frac{\varphi(n)}{n} = \prod_{p\mid n}\large(1 - \frac{1}{p}) \]首先考虑 \(\varphi(p^e)\),其中 \(p\) 是质数，\(e\) 是非负整数
如果要使 \(\gcd(p^e, k) \ne 1\), 只能让 \(k\) 等于 \(p\) 的倍数
在 \(1 \leqslant k \leqslant p^e\) 范围内， \(p\) 的倍数有 \(p,2p,3p,···,p^{e-1}p = p^e\) 总共 \(p^{e - 1}\) 个，所以
\[\varphi(p^e) = p^e - p^{e - 1} = p^e(1 - \frac{1}{p}) \]然后我们证明对于 \(\gcd (m,n) = 1\) 有 \(\varphi(mn) = \varphi(m)\varphi(n)\)，我们首先构造两个集合，第一个集合是模 \(mn\) 的最小正缩系 \(\Phi_mn\) ，第二个集合定义为
\[S = \{ (m,n) \mid m \in \Phi_m , n \in \Phi_n \} \]其中 \(\Phi_m, \Phi_n\) 分别是模 \(m, n\) 的最小正缩系，显然 \(\mid \Phi_{mn} \mid = \varphi(mn)\) 和 \(\mid S \mid = \varphi(m)\varphi(n)\)
如果我们证明存在一个双射 \(f: \Phi_{mn} \to S\) ,就证明了 \(\varphi(mn) = \varphi(m)\varphi(n)\)
我们让
\[f(a) = (a\!\!\!\!\!\mod m, a \!\!\!\!\!\mod n) \]首先我们用反证法证明 \(f\) 是单射，假设 \(a, b \in \Phi_{mn}\) 满足 \(a \ne b\) 且 \(f(a) = f(b)\) 那么
\[a \equiv b \pmod m \]\[a \equiv b \pmod n \]显然，因为 \(\gcd (m,n) = 1\) 我们能得出 \(a \equiv b \pmod {mn}\),这与我们的假设矛盾（因为 \(\Phi_{mn}\) 是模 \(mn\) 的缩系，\(a,b\) 是 \(\Phi_{mn}\) 的两个不同的元素，所以他们模 \(m,n\) 不同余）。接下来，中国剩余定理告诉我们
如果正整数 \(r_1,r_2\) 和正整数 \(\gcd(n_1,n_2) = 1\) ,同余方程组
\[x \equiv r_1 \pmod {n_1} \]\[x \equiv r_2 \pmod {n_2} \]在 \(0 \leqslant x < n_1n_2 范围内有且只有一个解\)
通过中国剩余定理我们能够证明 \(f\) 是满射， 所以 \(f\) 是双射
所以对于 \(\gcd (m,n) = 1\) 就有 \(\varphi(mn) = \varphi(m) \varphi(n)\)，假设 \(n\) 的标准分解为
\[n = 2^{e_1} \times 3^{e_2} \times 5^{e_3} \times ··· = \prod^{\infty}_{k = 1}p_k^{e_k} \]其中 $e_1, e_2， ··· \in \mathbb{N} $， 那么
\[\varphi(n) = \varphi(\prod^{\infty}_{k = 1}p_k^{e_k}) = \prod^{\infty}_{k = 1}\varphi(p_k^{e_k}) = \prod^{\infty}_{k = 1}p_k^{e_k}(1 - \frac{1}{p_k}) \]\[= (\prod^{\infty}_{k = 1}p_k^{e_k})\prod^{\infty}_{k = 1}(1 - \frac{1}{p_k}) = n \times \prod^{\infty}_{k = 1}(1 - \frac{1}{p_k}) \]证毕。