同余、中国剩余定理

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

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