欧拉定理
ddxrS
·
·
个人记录
更好的阅读体验 \texttt{blog} 的
### 前置芝士
莱昂哈德·欧拉(雾；互质；最大公因数；最小公倍数；裴蜀定理(雾。
### 正文
**欧拉定理(Euler's theorem)**，又称为费马-欧拉定理或欧拉函数定理。
如果有正整数 $n$ 和整数 $a$，且 $n$ 和 $a$ 互质，有：
$$
a^{\varphi(n)}\equiv1\ \pmod n
$$
其中 **欧拉函数** $\varphi(n)$ 是小于 $n$ 的正整数中和 $n$ 互质的数的个数。
---
我们需要了解几个概念：
#### 0.翡翠定理（Bézout's lemma）
（您可以不看）
对于不为 $0$ 整数 $a,b$，存在整数 $x,y$，使得 $ax + by = gcd(a,b)$。
证明：略。
应用：
[CF510D Fox And Jumping](https://www.luogu.com.cn/problem/CF510D)
化简题意：选择若干数，使得这些数通过数次相加或相减得出的绝对值为 $1$。
不难想到翡翠定理。可以推出，如果 $a,b$ 互质，那么一定存在整数 $x,y$，使得 $ax+by=1$。
由此得出了若选择的卡牌的数通过数次相加或相减得出的绝对值为 $1$，那么这些数一定互质，此时可以考虑动态规划求解。
#### 1.唯一质数分解定理（Unique factorisation theorem）
任何一个正整数 $n \ge 2$，都可以被分解成若干质数的积。
$$
n = 2 ^ {e_1} \times 3 ^ {e_2} \times 5 ^ {e_3} \times \cdots = \displaystyle \prod ^ {\infty} _ {k=1} {{p_k}^{e_k}}
$$
其中，$e_1,e_2,\cdots \in \Bbb{N}$，我们称这个分解为 $n$ 的标准分解。
#### 2.同余关系（Congruence relations）
整数 $a$ 和整数 $b$ 除以整数 $m$ 的余数相同，则称 $a,b$ 模 $m$ 同余，计作：
$$
a \equiv b\ (\bmod\ m)
$$
若对于整数 $a_1,a_2,b_1,b_2$ 有：
$$
a_1 \equiv b_1\ \pmod m,a_2 \equiv b_2\ (\bmod\ m)
$$
则它们相加：
$$
a_1 + a_2 \equiv b_1 + b_2\ (\bmod\ m)
$$
它们相乘：
$$
a_1a_2 \equiv b_1b_2\ (\bmod\ m)
$$
通过以上性质，我们能知道，如果 $a \equiv b (mod\ m)$ 那么
$$
P(a) \equiv P(b)\ (\bmod\ m)
$$
对于任意整数系多项式 $P(x)$ 都成立。
需要注意，如果整数 $a,b,c$ 满足：
$$
ac \equiv bc\ (\bmod\ m)
$$
那么，只有当 $m,c$ 互质时才能把两边的 $c$ 约掉得到 $a \equiv b\ (\bmod\ m)$。
#### 3.同余类(Residue class)、完全剩余系(Complete residue system)、缩剩余系(Reduced residue system)
通过一个整数模 $n$ 的余数，我们可以把所有的整数分成 $n$ 类。记
$$
\overline{r}_n = \{m\in \Bbb{Z} |mn + r\}
$$
为模 $n$ 与 $r$ 的 **同余类** 举个栗子：
$$
\overline{4}_{10} = \{\dots,-16,-6,-4,14,24,\dots \}
$$
是模 $10$ 余 $4$ 的同余类。
从 $\overline{0}_n,\overline{1}_n,\overline{2}_n,\dots,\overline{(n-1)}_n$ 中各挑一个出来就组成了一个模 $n$ 的**完全剩余系** $R_n$。
$$
R_n = \{r_0,r_1,\dots,r_{n-1}\}
$$
其中 $r_0 \in \overline{0}_n,r_1 \in \overline{1}_n,\dots,r_{n-1} \in \overline{(n-1)}_n$，也就是 $n$ 个模 $n$ 相互不同余的整数组成一个模 $n$ 的完全剩余系。
我们称 $R_n = \{0,1,2,\dots,n-1\}$ 为模 $n$ 的**最小非负完全剩余系**。
取一个模 $n$ 的完全剩余系 $R_n$，取出里面所有和 $n$ 互质的数，这些数组成一个模 $n$ 的**缩剩余系（缩系）**，记为 $\Phi_n$。
$$
\Phi_n=\{c_1,c_2,\dots,c_{\varphi(n)}\}
$$
其中 $\varphi(n)$ 是欧拉函数。
如果缩剩余系 $\Phi_n=\{c_1,c_2,\dots,c_{\varphi(n)}\}$ 满足 $1 \le c_1,c_2,\dots,c_{\varphi(n)}\le n-1$，那么称其为模 $n$ 的**最小正缩剩余系（最小正缩系）**
#### 4.欧拉函数(Euler's totient function)
对于正整数 $n$，$\varphi(n)$ 代表小于 $n$ 的正整数中和 $n$ 互质的数的个数，则这个函数被称为**欧拉函数**。根据定义，我们可以写出
$$
\varphi(n)=n\prod_{p|n,p\text{为质数}}(1-\frac{1}{p})
$$
欧拉函数的性质：
- 如果 $n \ge 3$ 那么 $\varphi(n)$ 是偶数。
- 如果正整数 $n | N$ 那么 $\varphi(n) | \varphi(N)$。
- 对于正整数 $a,n$ 有 $n|\varphi(a^n-1)$。
- 特别的，对于正整数 $n,m$ 且 $n,m$ 互质，那么 $\varphi(nm)=\varphi(n)\varphi(m)$，这也是积性函数的定义。
---
### 欧拉定理
如果有正整数 $n$ 和整数 $a$，且 $n$ 和 $a$ 互质，有：
$$
a^{\varphi(n)}\equiv1\ (\bmod\ n)
$$
其中 $\varphi(n)$ 是**欧拉函数**。
证明：
考虑模 $n$ 的最小正缩剩余系
$$
\Phi_n=\{c_1,c_2,\dots,c_{\varphi(n)}\}
$$
已知 $\gcd(a,n)=1$ 我们在 $\Phi_n$ 的每个元素前面都乘一个 $a
a\Phi_n=\{ac_1,ac_2,\dots,ac_{\varphi(n)}\}
利用反证法可以证明 a\Phi_n 也是模 n 的缩剩余系，假设
ac_i\equiv ac_j(\bmod\ n)
其中 i\not=j，因为 a,n 互质，两边可以同时消掉 a
c_i\equiv c_j(\bmod\ 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(\bmod\ n)
显然 \gcd(n,\prod^{\varphi(n)}_{i=1}c_i)=1 所以两边消掉
a^{\varphi(n)}\equiv1(\bmod\ n)
证毕。
是不是很简单？
如果 n=p 是一个质数，我们就可以推出 费马小定理（Fermat's little theorem）。
如果 p 是质数，那么 a^{p-1}\equiv1(\bmod\ p)。
证明：
对 a 使用数学归纳法。
当 a=1，显然成立。
假设 p|(a^p-a)，考虑
(a+1)^p-(a+1)
根据二项式定理展开第一项
\begin{aligned}
(a+1)^p-(a+1)&=\sum^{p}_{k=0}C^{k}_{p}a^k-a-1\\
&=\sum^{p-1}_{k=1}C^{k}_{p}a^k+(a^p-a)
\end{aligned}
由于 C^{k}_{p}=\cfrac{p!}{k!(p-k)!} 且 p 是质数，所以
p|C^k_p,1\le k\le p-1
即
p|\sum^{p-1}_{k=1}C^{k}_{p},p|(a^p-a)
所以
p|(a+1)^p-(a+1)
根据数学归纳法，对任意 a 都成立 p|(a^p-a)，证毕。
进一步，若 gcd(a,p)=1，则 p|(a^{p-1}-1) 即 a^{p-1}\equiv1(\bmod\ p)。
费马小定理通常用来检验一个数是否是素数，是素数的必要非充分条件。
然而满足费马小定理检验的数未必是素数，这种合数叫做卡迈克尔数（Carmichael Number），也是伪素数（伪质数），最小的卡迈克尔数是341。
那么，欧拉定理有哪些应用？
求 8^{7^{6^{5^{4^{3^{2^{1}}}}}}} 的最后三位。
答案是 008。
因为
7^{4n}=(50-1)^{2n}\equiv1(\bmod\ 100)
从 \varphi(125)=125()1-\frac{1}{5}=100 我们能得到
8^{7^{4n}}\equiv8(\bmod\ 125)
因为 125|8^{7^{4n}}-8 以及 8^{7^{4n}}-8 且 \gcd(8,125)=1
1000|8^{7^{4n}}-8
所以
8^{7^{4n}}\equiv8(\bmod\ 1000)
又因为 4|6^{5^{4^{3^{2^{1}}}}}，所以 8^{7^{6^{5^{4^{3^{2^{1}}}}}}} 模 1000 的值就为 8。
最后三位就是 008。