同余、中国剩余定理一、同余 (Congruence)
1. 令 \(\mathsf{a,\ b,\ m}\) 为整数，且 $ \mathsf{m \neq 0}$ 。当满足 \(\mathsf{m \mid (a-b)}\) 时，称 a 与 b 模 m 同余，写作 \(\mathsf{a \equiv b \ mod \ m}\)
例子：
\(\mathsf{3 \equiv 27\ mod\ 12}\)， \(\mathsf{-3 \equiv 11\ mod\ 7}\)
2. 基本性质：同余兼容常用加法与乘法运算。如果 \(\mathsf{a \equiv b\ (mod\ m)}\) 并且 \(\mathsf{c \equiv d\ (mod\ m)}\)，那么 \(\mathsf{a+c \equiv b+d\ (mod\ m)}\)，\(\mathsf{ac\equiv bd\ (mod\ m)}\)
例子：
$\mathsf{4 + 12 \equiv 26 + 1\ (mod\ 11)} $， \(\mathsf{4 \times 12 \equiv 26 \times 1\ (mod\ 11)}\)
证明：
\(\mathsf{a = b + mk，c = d + ml，a + c = b + d + m(k + l)}\)
\(\mathsf{ac = bd + bml + dmk + m^{2}kl = bd + m(bl + dk + mkl)}\)
3. 同样地：如果 \(\mathsf{a \equiv b\ (mod\ m)}\)，那么 \(\mathsf{a^{k} \equiv b^{k}\ (mod\ m)}\)
4. 然而，下面的推论是错误的：
\(\qquad\)如果 \(\mathsf{a \equiv b\ (mod\ m)}\) 并且 \(\mathsf{c \equiv d\ (mod\ m)}\)，那么 \(\mathsf{a^{c} \equiv b^{d}\ (mod\ m)}\)
\(\qquad\)如果 \(\mathsf{ax \equiv bx\ (mod m)}\)，那么 \(\mathsf{a \equiv b\ (mod\ m)}\)
例子：
\(\mathsf{4^{12} \neq 4^{1}\ (mod 11)}\)， \(\mathsf{8^{2} \neq 3^{7}\ (mod\ 5)}\)， \(\mathsf{5 \times 2 \equiv 2 \times 2\ (mod\ 6)}\)
二、剩余系统
模 m 的完全剩余系：一组整数 \(\mathsf{a_{1},\ a_{2},\ \cdots\ a_{m}}\)，满足当 \(\mathsf{i \neq j}\) 时，\(\mathsf{a_{i} \neq a_{j}\ mod\ m}\)，即 m 个数两两互不同余。
模 m 的简化剩余系：m 的完全剩余系中与 m 互素的数构成的子集。
例子：
如果 \(\mathsf{m=9}\)，完全剩余系：\(\mathsf{\{1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9 \}}\) 简化剩余系：\(\mathsf{\{ 1,\ 2,\ 4,\ 5,\ 7,\ 8 \}}\)
如果 \(\mathsf{m=10}\)，完全剩余系：\(\mathsf{\{1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,\ 10 \}}\) 简化剩余系：\(\mathsf{\{ 1,\ 3,\ 7,\ 9 \}}\)
三、欧拉函数
1. 简化剩余系中元素个数，用 \(\mathsf{\phi(m)}\) 表示。
例子：
\(\mathsf{\phi(9)=6}\)， \(\mathsf{\phi(10)=4}\)
四、欧拉定理
1. 如果 \(\mathsf{gcd(a,m)=1}\)，那么 \(\mathsf{a^{\phi(m)} \equiv 1\ mod\ m}\)
例子：
\(\mathsf{3^{\phi(10)}=81 \equiv 1 mod 10}\)
2. 引理：如果 \(\mathsf{gcd(a,m)=1}\) 并且 \(\mathsf{r_{1}\ r_{2}\ \cdots r_{k}}\) 是模 m 的简化剩余系，\(\mathsf{k=\phi(m)}\)。那么 \(\mathsf{ar_{1}\ ar_{2}\ \cdots ar_{k}}\) 也是模 m 的简化剩余系。
例子：
模 10 的简化剩余系统 \(\mathsf{s=\{ 1,\ 3,\ 7,\ 9\}}\)， \(\mathsf{7s=\{7,\ 1,\ 9,\ 3\}}\)
证明：
因为 \(\mathsf{gcd(r,m)}\) 和 \(\mathsf{gcd(a,m)=1}\)，所以 \(\mathsf{gcd(ar,m)=1}\)。如果 \(\mathsf{ar_{i} \equiv ar_{j}\ mod\ m}\)，那么 \(\mathsf{m\ |\ ar_{i}-ar_{j}=a(r_{i}-r_{j})}\)
如果 \(\mathsf{gcd(a,m)=1}\)，那么 \(\mathsf{m \mid r_{i}-r_{j}\ \Rightarrow\ r_{i} \equiv r_{j}\ mod\ m}\)，仅当 \(\mathsf{i=j}\) 时成立。所以 \(\mathsf{ar_{i}}\) 全部与 m 互素并且在模 m 下不同。
五、费马小定理 (Fermat’s little Theorem)
1. 如果 p 为素数 a 为整数，则 \(\mathsf{\phi(p)=p-1，\phi(p^{n})=(p-1)p^{n-1}}\)，那么 \(\mathsf{a^{p} \equiv a(mod\ p)}\)
例子：
\(\mathsf{3^{5} \equiv 3\ mod\ 5}\)， \(\mathsf{2^{11} \equiv 2\ mod\ 11}\)
六、模逆元 (Inverse of elements)
1. 如果 \(\mathsf{gcd(a,m)=1}\)，那么在模 m 下，存在唯一的一个整数 b ，使 \(\mathsf{ab \equiv 1\ mod\ m}\)，则 b 是 a 的模逆元，用 \(\mathsf{\frac{1}{a}}\) 或 \(\mathsf{a^{-1}\ mod\ m}\) 表示。
例子：
\(\mathsf{\frac{1}{5}\ mod\ 7=5^{-1}\ mod\ 7=3}\)
存在性：
因为 \(\mathsf{gcd(a,m)=1}\)，对于某些整数 \(\mathsf{x，y}\)，\(\mathsf{ax+my=1}\)，所以 \(\mathsf{ax \equiv 1\ mod\ m}\) 令 \(\mathsf{b=x}\) 即可
唯一性：
如果 \(\mathsf{ab_{1} \equiv 1\ mod\ m}\) 并且 \(\mathsf{ab_{2} \equiv 1\ mod\ m}\)
那么 \(\mathsf{ab_{1} \equiv ab_{2}\ mod\ m \Rightarrow m \mid a(b_{1}-b_{2})}\)
因为 \(\mathsf{gcd(m,a)=1}\)，$\mathsf{m \mid b_{1}-b_{2} \Rightarrow b_{1} \equiv b_{2}\ mod\ m} $
七、威尔逊定理 (Wilson’s Theorem)
- 如果 p 是素数，那么 \(\mathsf{(p-1)! \equiv -1\ mod\ p}\)
例子：
$ \mathsf{4!=24 \equiv -1\ mod\ 5}$
- 引理：同余方程 \(\mathsf{x^{2} \equiv 1\ mod\ p}\)，仅有解 \(\mathsf{x \equiv \pm1\ mod\ p}\)
证明：
\(\mathsf{x^{2} \equiv 1\ mod\ p \Rightarrow p \mid (x^{2}-1) \Rightarrow p \mid (x-1)(x+1) \Rightarrow p \mid x \pm 1 \Rightarrow x \equiv \pm1\ mod\ p}\)
八、同余方程(组)
- 同余方程(组)的形式为：\(\mathsf{a_{n}x^{n}+a_{n-1}x^{n-1}+ \cdots +a_{0} \equiv 0\ mod\ m}\)，其中 \(\mathsf{\{a_{n},\ a_{n-1},\ \cdots,\ a_{0} \}}\) 为整数。同余方程(组)的解是模 m 下满足方程的整数或剩余类。
例子：
\(\mathsf{x^{2} \equiv -1\ mod\ 13}\) 的解为 \(\mathsf{\{5,\ 8 \}}\)， \(\mathsf{x^{2} \equiv 1\ mod\ 15}\) 的解为 \(\mathsf{\{\pm1,\ \pm4\ mod\ 15 \}}\)
九、线性同余方程组 (度为一)
1. 定理：令 \(\mathsf{g=gcd(a,m)}\)，线性同余方程组 \(\mathsf{ax \equiv b\ mod\ m}\) 解存在当且仅当 \(\mathsf{g \mid b}\)，且在模 m 下解一共有 g 个。
例子：
\(\mathsf{4x \equiv 5\ mod\ 10}\) 无解，因为 \(\mathsf{g=gcd(4,10) \nmid 5}\)
\(\mathsf{4x \equiv 6\ mod\ 10}\) 有解 \(\mathsf{x=4}\)，实际上有 \(\mathsf{g=2}\) 个解，另一个解为 \(\mathsf{x=9}\)
证明：
假设 $\mathsf{g \nmid b} $，
假设 \(\mathsf{x_{0}}\) 是一个解 \(\mathsf{\Rightarrow}\) 对于某些整数 k，\(\mathsf{ax_{0}=b+mk}\)
因为 \(\mathsf{g \mid a,\ g \mid m,\ g}\) 整除 \(\mathsf{ax_{0}-mk=b}\)，与假设矛盾，故 \(\mathsf{g \mid b}\)
对于整数 \(\mathsf{x_{0},\ y_{0},\ g=ax_{0}+my_{0}}\)
设 \(\mathsf{b=b^{‘}g}\)，则 \(\mathsf{b=b^{‘}g=b^{‘}(ax_{0}+my_{0})=a(b^{‘}x_{0})+m(b^{‘}y_{0})\ \Rightarrow \ a(b^{‘}x_{0}) \equiv b\ (mod\ m)}\)
所以，\(\mathsf{x=b^{‘}x_{0}}\) 是一个解。
证明确实存在 g 个解：
假设有一个解 \(\mathsf{x_{1}}\)，那么 \(\mathsf{ax \equiv b \equiv ax_{1}\ mod\ m}\)，\(\mathsf{a(x-x_{1})=0\ (mod\ m)}\)
对于某些整数 k，\(\mathsf{a(x-x_{1})=mk}\)
\(\mathsf{g=gcd(a,m)\ \Rightarrow a=a^{‘}g，m=m^{‘}g}\) 所以 \(\mathsf{gcd(a^{‘},m^{‘}=1)}\)
则 \(\mathsf{a^{‘}g(x-x_{1})=m^{‘}gk\ \Rightarrow}\) 对于某些 k，\(\mathsf{a^{‘}(x-x_{1})=m^{‘}k}\)
所以 \(\mathsf{m^{‘} \mid x-x_{1}}\) ，则 \(\mathsf{x \equiv x_{1}\ mod\ m^{‘}}\)
所以，所有的解为：\(\mathsf{x_{1},\ x_{1}+m^{‘},\ x_{1}+2m^{‘},\ \cdots,\ x_{1}+(g-1)m^{‘} }\)
十、欧几里得扩展算法 (Extended Euclidean Algorithm)
1. 欧几里得扩展算法用于获得模逆元 \(\mathsf{a^{-1}\ mod\ n}\)，当 \(\mathsf{gcd(a,n)=1}\) 时。
例子：
\(\mathsf{41=1 \times 23 + 18}\)
\(\mathsf{23=1 \times 18 + 5}\)
\(\mathsf{18=3 \times 5 + 3}\)
\(\mathsf{5=1 \times 3 + 2}\)
\(\mathsf{3=1 \times 2 + 1}\)
\(\mathsf{2=2 \times 1}\)
\(\mathsf{1=3-1 \times 2=3-(5-1 \times 3)=-1 \times 5 + 2 \times 3}\)
\(\mathsf{=-1 \times 5 +2 \times (18-3 \times 5) =2 \times 18 – 7 \times 5 }\)
\(\mathsf{= 2 \times 18 – 7 \times (23-1 \times 18)=-7 \times 23 + 9 \times 18}\)
\(\mathsf{=-7 \times 23 + 9 \times (41 – 1 \times 23)=9 \times 41 – 16 \times 23}\)
所以，\(\mathsf{23^{-1}\ mod\ 41 = -16\ or\ 25}\)
伪代码：
function inverse(a, n)t := 0;newt := 1;r := n;newr := a;while newr != 0quotient := r div newr(t, newt) := (newt, t - quotient * newt)(r, newr) := (newr, r - quotient * newr)if r > 1 then return "a is not invertible"if t < 0 then t := t + nreturn t十一、中国剩余定理 (Chinese Remainder Theorem)
1. 问题：
\(\mathsf{\qquad \begin{cases} x \equiv a_{1}\ (mod\ m_{1}) \\x \equiv a_{2}\ (mod\ m_{2}) \\ \cdots \qquad\qquad \cdots \\x \equiv a_{k}\ (mod\ m_{k}) \end{cases}}\)
2. 解决方法(中国剩余定理)：
\(\mathsf{\qquad M_{i}= \frac{\prod m_{i}}{m_{i}}，y_{i}=M_{i}^{-1}\ mod\ m_{i}，x=\sum a_{i}M_{i}y_{i}\ mod\ (\prod m_{i})}\)
例子：
\(\mathsf{\begin{cases} x \equiv 5 \quad (mod\ 7) \\x \equiv 3 \quad (mod\ 11) \\x \equiv 10 \quad (mod\ 13) \end{cases}}\)
| sn | a | m | M | y |
|---|---|---|---|---|
| 1 | 5 | 7 | 143 | 5 |
| 2 | 3 | 11 | 91 | 4 |
| 3 | 10 | 13 | 77 | 12 |
\(\qquad\)所以，结果 \(\mathsf{(\sum aMy)}\) 在模 1001 下为 894
\(\mathsf{\qquad \begin{cases} 894 \equiv 5 \quad (mod\ 7) \\894 \equiv 3 \quad (mod\ 11) \\894 \equiv 10 \quad (mod\ 13) \end{cases}}\)