同余、中国剩余定理

一、同余 (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)}\)

二、剩余系统

1. 模 m 的完全剩余系：一组整数 \(\mathsf{a_{1},\ a_{2},\ \cdots\ a_{m}}\)，满足当 \(\mathsf{i \neq j}\) 时，\(\mathsf{a_{i} \neq a_{j}\ mod\ m}\)，即 m 个数两两互不同余。

2. 模 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)

1. 如果 p 是素数，那么 \(\mathsf{(p-1)! \equiv -1\ mod\ p}\)

• 例子：

  $ \mathsf{4!=24 \equiv -1\ mod\ 5}$

2. 引理：同余方程 \(\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}\)

八、同余方程(组)

1. 同余方程(组)的形式为：\(\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 != 0
		quotient := 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 + n
	return 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}}\)