y 总在算法基础课数学知识章节第二节欧拉定理的一点补充以及详细证明
剩余系、同余、模逆元、欧拉定理、费马小定理
前置知识：
- 容斥原理与欧拉函数
- 从带余除法定理、贝祖定理、欧几里得引理到算术基本定理

剩余系

可以把剩余系想象成一个“余数的集合”。当我们用一个固定的整数（成为“模”）去除不同的整数时，得到的余数总是落在一定的范围内。这个范围内所有可能的余数的集合，就叫做一个剩余系。
更正式的说，给定一个正整数 $n$ （称为模），任何整数除以 $n$ 得到的余数都在 0, 1, 2, ...., n-1 这$n$ 个数之间。这个集合 $\left\{ 0, 1,2,\dots n-1 \right\}$ 就构成模 $n$ 的一个完全剩余系

举个例子：
假设我们的模 n = 5。 那么：

• 7 除以 5 的余数是 2
• 12 除以 5 的余数是 2
• -3 除以 5 的余数是 2 (因为 -3 = -1 * 5 + 2)
• 10 除以 5 的余数是 0

可以看到，无论我们用哪个整数除以 5，余数总是 0, 1, 2, 3, 4 这五个数中的一个。所以，{0, 1, 2, 3, 4} 就是模 5 的一个完全剩余系。

完全剩余系和简化剩余系：

• 完全剩余系: 包含了模 n 所有可能的余数，即 0 到 n-1。
• 简化剩余系 (也叫既约剩余系): 只包含与模 n 互质的余数。也就是说，简化剩余系中的每个数都与 n 没有共同的因子（除了1）。

继续上面的例子：

对于模 5 的完全剩余系 {0, 1, 2, 3, 4} 来说，

• 1, 2, 3, 4 都与 5 互质。
• 0 和 5 不互质 (因为它们有共同的因子 5)。

所以，模 5 的一个简化剩余系是 {1, 2, 3, 4}。

同余

定义：$a \equiv b(mod\ n)$ 表示 $a-b$ 可以被 $n$ 整除，也就是说存在一个整数 $k$ 使得 $a-b=k\times n$

模逆元

先介绍一下 逆元（Inverse） 的一般概念
在数学中，逆元的概念是指一个元素，当与另一个元素进行某种运算时，得到单位元（或恒等元）。单位元是进行运算后不改变任何元素的值的元素。
- 加法逆元：对于加法，单位元是 0 ， $a$ 的加法逆元是 $-a$ ，因为 $a+(-a)=0$
- 乘法逆元：对于乘法，单位元是 1， $a$ 的乘法逆元是 $\frac{1}{a}$ ，因为 $a\times \frac{1}{a} = 1$

模逆元（一般指模乘法逆元）是指对于整数 $a$ 和正整数 $m$ ，存在一个整数 $x$ 使得：
$$a\times x \equiv 1(mod\ m)$$
此时，$x$ 称为 $a$ 在模 $m$ 下的逆元 ，记作 $a^{-1}$
模逆元存在的充要条件是 $a$ 和 $m$ 互质，即 $gcd(a,m)=1$ 。若不互质则不存在模逆元。

证明 $a$ 和 $m$ 互质为什么是充要条件：

必要性证明（若模逆元存在，则 $a$ 和 $m$ 必须互质）：
假设存在整数 $x$ 使得： $a\times x\equiv 1(mod\ m)$
根据同余的定义，存在整数 $k$ 使得 ： $a\times x=1+k\times m\implies a\times x-k\times m=1$
根据贝祖定理 $a\times x+(-k)\times m=1\implies gcd(a,m)=1$ ，即 $a,m$ 互质

充分性证明 （若 $a$ 和 $m$ 互质，则模逆元存在）
若 $gcd(a,m)=1$ 根据贝祖定理，存在整数 $x$ 和 $y$ 使得：
$$a\times x+m\times y=1$$
将等式两边对 $m$ 取模： $a\times x\equiv 1(mod\ m)$
此时 $x$ 为 $a$ 在模$m$ 下的逆元

模逆元的性质

模逆元有个重要的性质：
假设 $a\times b\equiv a\times c(mod\ n)$ 并且 $gcd(a,n)=1$ 时，可以像普通代数那样消去 $a$ 得到 $b\equiv c(mod\ n)$
证明：
由于 $gcd(a,n)=1$ ，所以存在 $a$ 模 $n$ 的逆元 $a^{-1}$， $a\times a^{-1}\equiv 1(mod\ n)$
因此：
$$\begin{align} a\times b=a\times c(mod\ n)\implies a\times b-a\times c&=k_{1}\times n \\ a^{-1}\times(a\times b-a\times c)&=a^{-1}\times(k_{1}\times n) \\ a^{-1}\times a\times b-a^{-1}\times a\times c&=a^{-1}\times k_{1}\times n \end{align}$$
因为 $a^{-1}\times a\equiv1(mod\ n)$ ，所以 $a^{-1}\times a=k_{2}\times n+1$ ，代入等式
$$\begin{align} (k_{2}\times n+1)\times (b-c) & = a^{-1}\times k_{1}\times n \\ k_{2}\times b\times n+b-k_{2}\times c\times n-c & =a^{-1}\times k_{1}\times n \\ b-c+(k_{2}\times b-k_{2}\times c)\times n & =a^{-1}\times k_{1}\times n \\ \end{align}$$
令 $k_{3}=k_{2}\times b-k_{2}\times c$，代入等式
$$\begin{align} b-c+k_{3}\times n & =a^{-1}\times k_{1}\times n \\ b-c & =a^{-1}\times k_{1}\times n-k_{3}\times n \\ b-c & =(a^{-1}\times k_{1}\times k_{3})\times n \end{align}$$
由于 $a^{-1},k_{1},k_{3}$ 都是整数，$n$ 整除 $b-c$ ，也就是 $b\equiv c(mod\ n)$

代表元与同余类（剩余类）

同余类的定义

注意剩余系和剩余类名字容易混淆，它们是完全不同的概念

在模 $n$ 的意义下，所有与整数 $a$ 同余的数构成一个同余类（或剩余类），记作 $[a]$ 。
例：模 5 的同余类包括 $[0]=\left\{ \dots,-10,-5,0,5,10,\dots \right\}$ , $[1]=\left\{ \dots,-9,-4,1,6,11,\dots \right\},\dots$
每个同余类包含无数个整数，但它们的模 $n$ 余数相同

代表元

在同余类 $[a]$ 中，任何一个元素都可以作为这个类的代表元。例如 在模 $5$ 的同余类 $[2]$ 中，$2,7,-3\dots$ 都是该类的代表元，因为它们满足 $2 \equiv 7 \equiv -3(mod\ 5)$

标准代表元：代表元不唯一，但通常选择最小非负整数 作为标准代表元
任意代表元：可以是同余类中的任意整数，无论正负大小

简化剩余系

重新对简化剩余系下个定义：
模 $n$ 的简化剩余系是一个集合 $\left\{ r_{1},r_{2},\dots,r_{\varphi(n)} \right\}$ ，满足：

1. 每个 $r_{i}$ 与 $n$ 互质，即 $gcd(r_{i},n)=1$ ，
2. 在模 $n$ 下 , $r_{i} \not\equiv r_{j} \left( mod\ n \right)(i \neq j)$ , 即每个同余类出一个代表元
3. 集合的元素个数等于 $\varphi(n)$ ， 即要覆盖所有同余类

欧拉定理

首先回顾下欧拉函数：$\varphi(N)$ 表示小于或等于 $N$ 的正整数中，与 $N$ 互质（即最大公约数为 1）的数的个数
ps：显然 $\varphi(N)$ 也就是 $N$ 的简化剩余系的模

若 $a$ 与 $n$ 互质，则 $a^{\varphi(n)} \equiv 1(mod\ n)$

证明：
$n$ 的简化剩余系为 $\left\{ r_{1},r_{2},\dots,r_{\varphi(n)} \right\}$ （小于 $n$ 且与 $n$ 互质的所有整数的集合）
现在设想集合 $\left\{ ar_{1},ar_{2},\dots,ar_{\varphi(n)} \right\}$ ，这个集合具有如下性质

• 每个 $ar_{i}$ 都与 $n$ 互质：因为 $a$ 和 $r_{i}$ 都与 $n$ 互质，所以他们的乘积 $ar_{i}$ 也与 $n$ 互质（可以用算术基本定理证得，由于 $a$ 和 $r_{i}$ 都与 $n$ 互质，那么 $a$ 和 $n$ 没有公共质因子，$r_{i}$ 和 $n$ 也没有公共质因子，那么 $ar_{i}$ 和 $n$ 没有公共质因子）
• $ar_{i}$ 模 $n$ 不同余：反证法，假设存在 $i$ 和 $j$ ，$i\neq j$ , 使得 $ar_{i}\equiv ar_{j}(mod\ n)$ ，因为 $a$ 与 $n$ 互质，可以两边同时乘以 $a$ 的 模$n$ 逆元，所以 $r_{i} \equiv r_{j}(mod\ n)$ 。但 $r_{i}$ 和 $r_{j}$ 都是小于 $n$ 的正整数，且 $r_{i} \neq r_{j}$ ，产生矛盾。所以 $ar_{i}$ 模 $n$ 不同余

因此 $\left\{ r_{1},r_{2},\dots,r_{\varphi(n)} \right\}$ 和 $\left\{ ar_{1},ar_{2},\dots,ar_{\varphi(n)} \right\}$ 都是模 $n$ 的简化剩余系，他们包含的元素模 $n$ 相同，只是顺序可能不同。因此他们的乘积 模 $n$ 一定相同：
$ar_{1}\times ar_{2}\times\dots \times ar_{\varphi(n)}\equiv r_{1}\times r_{2}\times\dots \times r_{\varphi(n)}(mod\ n)$
等式左边展开：$a^{\varphi(n)}\times (r_{1}\times r_{2}\times\dots \times r_{\varphi(n)})\equiv r_{1}\times r_{2}\times\dots \times r_{\varphi(n)}(mod\ n)$
由于 $r_{1},r_{2},\dots,r_{\varphi(n)}$ 都与 $n$ 互质，所以他们的乘积也与 $n$ 互质。因此，可以两边同时乘以 $(r_{1}\times r_{2}\times\dots \times r_{\varphi(n)})$ 的模 $n$ 逆元，得到：$a^{\varphi(n)}\equiv 1(mod\ n)$

费马小定理

费马小定理是欧拉定理的特例

若 $a$ 与 $p$ 互质，那么 $a^{(p-1)}\equiv 1(mod\ p)$
证明：当 $n$ 是质数 $p$ 时，$\varphi(p) = p-1$ ，代入欧拉定理可以直接得到费马小定理