同余 学习笔记

数学 数论 同余 学习笔记 逆元

---

定义

若整数 $a$ 与整数 $b$ 除以正整数 $m$ 的余数相同，则称 $a,b$ 模 $m$ 同余，记作 $a\equiv b\pmod{m}$。

---

同余类与剩余系

同余类（剩余类）： 对于 $\forall a \in [0,m-1]$，集合 $\{ a+km\}(k \in \mathbb{Z})$ 中的所有数模 $m$ 同余，余数都为 $a$，该集合称为模 $m$ 的一个同余类，简记为 $\overline a$。

完全剩余系： 模 $m$ 的同余类共有 $m$ 个，分别为 $\overline{0},\overline{1},\overline{2},\overline{3},\cdots ,\overline{m-1}$，从这 $m$ 个集合中分别取出 1 个数，构成一个大小为 $m$ 的集合，这个集合称为模 $m$ 的一个完全剩余系。

简化剩余系： 模 $m$ 的完全剩余系中与 $m$ 互质的数构成的一个子集。
若一个模 $m$ 的同余类 $\overline{i}$ 中的所有数都与 $m$ 互质（事实上只要该同余类中的一个数与 $m$ 互质，则该同余类中的所有数都会与 $m$ 互质，证明），则称 $\overline{i}$ 为 与模 $m$ 互质的剩余类 。在所有 与模 $m$ 互质的剩余类 中分别取出一个数，构成一个大小为 $\phi{(m)}$ 的集合，这个集合称为模 $m$ 的一个简化剩余系。
例如，模 10 的一个简化剩余系为 $\{1,3,7,9\}$，另一个简化剩余系为 $\{1,13,27,39\}$。

简化剩余系关于模 $m$ 乘法封闭。
证明：
从一个模 $m$ 的简化剩余系中取出两个数 $x,y$，
由于 $gcd(x,m)=1,\ gcd(y,m)=1$，所以 $gcd(x*y,m)=1$，
所以 $gcd(x*y\ mod\ m,m)=1$，
故 $x*y$ 模 $m$ 的余数也属于 $m$ 的简化剩余系。

---

欧拉定理

若正整数 $a,n$ 互质，则

$$a^{\phi(n)} \equiv 1\pmod{n}$$

证明：
设 $\{r_1,r_2,r_3,\cdots ,r_{\phi(n)}\}$ 为模 $n$ 的一个简化剩余系，求证 $\{ar_1,ar_2,ar_3,\cdots ,ar_{\phi(n)}\}$ 为模 $n$ 的一个简化剩余系。
反证法：
若 $\forall r_i,r_j\ (i\neq j),\ ar_i \equiv ar_j \pmod{n}$，
由于 $a,n$ 互质，所以 $r_i\equiv r_j \pmod{n}$，与条件矛盾，
所以 $ar_i,ar_j$ 属于模 $m$ 的不同剩余系，

因为 $a,n$ 互质, 所以 $a$ 属于 $n$ 的一个简化剩余系,
又因为简化剩余系关于模 $n$ 乘法封闭, 所以 $ar_i$ 属于 $n$ 的一个简化剩余系.
所以 $\{ar_1,ar_2,ar_3,\cdots ,ar_{\phi(n)}\}$ 为模 $n$ 的一个简化剩余系。

所以

$$a^{\phi(n)}r_1r_2r_3\cdots r_{\phi(n)}\equiv (ar_1)(ar_2)(ar_3)\cdots (ar_{\phi(n)})\equiv r_1r_2r_3\cdots r_{\phi(n)}\pmod{n}$$
由于 $r_1r_2r_3\cdots r_{\phi(n)}$ 与 $n$ 互质，
故
$$a^{\phi(n)}\equiv 1\pmod{n}$$
得证。

---

扩展欧拉定理

若 $a,p$ 为正整数，则

$$a^b\equiv \left\{ \begin{aligned} a^{b\mod \phi(p)}, && gcd(a,p)=1 \\ a^b, && b<\phi(p) \\ a^{b\mod \phi(p) +\phi(p)}, && b \ge \phi(p) \end{aligned} \right.$$
证明：（第一种情况）
设 $b=k\phi(p)+r$ ，则 $r=b\mod \phi(p)$。
所以 $a^b \equiv a^{k\phi(p)+r} \equiv (a^{\phi(p)})^k*a^r \equiv 1^k*a^r \equiv a^r \equiv a^{b\mod\phi(p)} \pmod{p}$，得证

---

费马小定理

若 $p$ 是质数，若正整数 $a$ 不是 $p$ 的倍数（$a,p$ 互质），则

$$a^{p-1} \equiv 1\pmod{p}$$
证明：
由欧拉定理可得：$a^{\phi(p)} \equiv 1 \pmod{p}$；
因为 $p$ 为质数，所以 $\phi(p)=p-1$；
所以 $a^{p-1} \equiv 1 \pmod{p}$，得证。

---

扩展欧几里得算法

用途

求解二元一次方程 $ax+by=c$, $(a,b \in \mathbb{Z})$

前置知识

贝祖定理 : 对于任意 $a,b \in \mathbb{Z}$, 存在 $x,y \in \mathbb{Z}$, 使得 $ax+by=gcd(a,b)$.

证明 (数学归纳法) :
首先, 考虑欧几里得算法的最后一步

---

乘法逆元

定义

对于整数 $a$，若 $ax\equiv 1 \pmod{m}$，则称 $x$ 为 $a$ 模 $m$ 的乘法逆元，记作 $a^{-1}\pmod{m}$

存在条件

对于整数 $a$，当且仅当 $a,m$ 互质时，存在 $a$ 模 $m$ 的乘法逆元。

证明：
设 $x$ 为 $a$ 模 $m$ 的逆元，则 $ax\equiv 1 \pmod{m}$，
该式子可转化为不定方程 $ax+my=1$，
根据贝祖定理可知，当 $gcd(a,m)|1$ 时，该方程有解，
所以 $gcd(a,m)=1$，得证。

求逆元

在上文证明逆元的存在条件时提到，同余方程 $ax\equiv 1 \pmod{m}$ 可转化为不定方程 $ax+my=1$，我们就可以用扩展欧几里得算法求解 $a$ 模 $m$ 的逆元。

特殊的，当 $m$ 为质数时，$a^{-1}\equiv a^{m-2} \pmod{m}$。
证明：
设 $ax\equiv 1 \pmod{m}$，
根据费马小定理

若 $p$ 是质数，若整数 $a$ 与 $p$ 互质，则 $a^{p-1} \equiv 1\pmod{p}$

可得，$ax\equiv a^{m-1} \pmod{m}$，
由于 $a,m$ 互质，所以，$x\equiv a^{m-2} \pmod{m}$，得证。