4.同余

德国大数学家高斯发明了同余式语言．这使得我们差不多能像处理等式一样来处理整除关系

1. 本章讨论同余的基本性质，描述如何进行同余式的算术运算
2. 研究含有未知数的线性同余方程
3. 研究线性同余方程组（古代中国数学难题），给出中国剩余定理的解法
4. 研究多项式同余方程
5. 提供一种使用同余语言分解整数的方法——波拉德 \(\rho\) 方法

1. 同余引言

在引人同余之前，人们研究整除关系所用的记号笨拙而且难用．而引人方便的记号对加速数论的发展起了帮助作用

设 m 是正整数，若 a 和 b 是整数，且 \(m|(a-b)\)，则称 a 和 b 模 m 同余

若 \(m|(a-b)\)，则记 \(a\equiv b\pmod m\)；若 \(m\nmid(a-b)\)，则记 \(a\not\equiv b\pmod m\)

1. 若 \(a\equiv b\pmod m\)，则 \(a\equiv b\pmod m\) 当且仅当存在整数 k，使得 \(a=b+km\)
2. 假设 m 是正整数，那么模 m 的同余满足如下性质：
   1. 自反性：若 a 是整数，则 \(a\equiv a\pmod m\)
   2. 对称性：若 a 和 b 是整数，且 \(a\equiv b\pmod m\)，则 \(b\equiv a\pmod m\)
   3. 传递性：若 a，b，c 是整数，且 \(a\equiv b\pmod m,b\equiv c\pmod m\)，则 \(a\equiv c\pmod m\)

(1) \(a\equiv b\pmod m\)，等价于 \(m|(a-b)\)，等价于存在 k 使得 \(km=a-b\)，等价于 \(a=b+km\)

(2.1) \(m|(a-a)=0\)，所以 \(a\equiv a\pmod m\)

(2.2) 若 \(a\equiv b\pmod m\)，则 \(m|(a-b)\)，从而存在整数 k 使得 \(km=a-b\)，即 \((-k)m=b-a\)，等价于 \(m|(b-a)\)，等价于 \(b\equiv a\pmod m\)

(2.3) 若 \(a\equiv b\pmod m,b\equiv c\pmod m\)，则有 \(m|(a-b),m|(b-c)\)，从而存在整数 k 和 l 使得 \(km=a-b,lm=b-c\)，于是 \((k+l)m=(a-b)+(b-c)=a-c\)，于是 \(a\equiv c\pmod m\)

\(\blacksquare\)

定理 (2) 意味着整数集合被分为 m 个不同的集合，这些集合称为模 m 剩余类（同余类）；同余类中任意两个整数都是模 m 同余的

设 m 是正整数，给定整数 a，有带余除法有 \(a=bm+r\)（\(0\le r\le m-1\)），称 r 为 a 的模 m 最小非负剩余，是 a 模 m 的结果

模 m 完全剩余系：模 m 完全剩余系是一个整数的集合，使得每个整数恰和此集合中的一个元素模 m 同余

模 m 剩余类：上述定理 (2) 将整数分为 m 个不同集合，这些集合称为模 m 剩余类（同余类），同余类中任意两个整数都是模 m 同余的；由 r 确定的同余类为 \(C_r=\{a~|~a=bm+r\}\)（\(m\in\mathbb N^+,r=0..m-1\)）

模 m 最小非负剩余：设 m 是正整数，给定整数 a，有带余除法有 \(a=bm+r\)（\(0\le r\le m-1\)），称 r 为 a 的模 m 最小非负剩余，是 a 模 m 的结果

（注：计算机科学中常用记号 \(a\mod m=r\)，表示 r 是 a 被 m 除所得的余数）

（注2：方程 \(a=bm+r\)，有 \(a\equiv r\pmod m\)；由于 \(0..m-1\) 中任意两个数都不是模 m 同余的，所有每个整数都和 \(0..m-1\) 其中一个整数模 m 同余，进而存在 m 个整数，其中每个整数都恰与 \(0..m-1\) 其中之一同余）

模 m 完全剩余系：一个模 m 完全剩余系是一个整数集合，使得每个整数都恰好与此集合中的一个元素模 m 同余

（注：\(\{0,\dots,m-1\}\) 称为最小非负剩余的集合，该集合是模 m 完全剩余系）

（注2：若 m 是正奇数，则 \(\left\{\frac{m-(2i+1)}2~|~i=0..2\lfloor\frac m2\rfloor\right\}\)（\(2\lfloor\frac m2\rfloor=m-1\)）称为模 m 绝对最小剩余的集合，也是一个模 m 完全剩余系）

（注3：若 k 是正整数，给定非负整数 m，对 m 做带余数除法有 \(m=tk+r\)(\(r=0..k-1\))，那么 \(\left\{\frac{m-(ik+r)}k~|~i=0..m-1\right\}\) 或 \(\left\{t-i~|~i=0..m-1\right\}\) 是也是模 m 的完全剩余系）

假设 a，b，c 是整数，m 是正整数，且 \(a\equiv b\pmod m\)，则：

1. \(a+c\equiv b+c\pmod m\)
2. \(a-c\equiv b-c\pmod m\)
3. \(ac\equiv bc\pmod m\)
4. \(a/c\equiv b/c\pmod{m/(m,c)}\)（当 \(c|a,c|b,c>0\)）
   1. 推论：\(a/c\equiv b/c\pmod{m}\)（当 \(c|a,c|b,c>0\)，\((m,c)=1\)）
   2. 推论2：\(a/c\equiv b/c\pmod p\)（当 \(c|a,c|b,c>0\)，p 是质数，且 \(c\le p-1\)）

证明：

假设 \(a\equiv b\pmod m\)，那么 \(m|(a-b)\)

(1) 由 \(a-b=(a+c)-(b+c)\)，有 \(m|[(a+c)-(b+c)]\)，蕴涵 \(a+c\equiv b+c\pmod m\)

(2) 由 \(a-b=(a-c)-(b-c)\)，有 \(m|[(a-c)-(b-c)]\)，蕴涵 \(a-c\equiv b-c\pmod m\)

(3) 由 \(a-b=ac-bc\)，有 \(m|(ac-bc)\)，蕴涵 \(ac\equiv bc\pmod m\)

(4) 设 \(d=(m,c)\)

由 \(m|(a-b)\) 和 \(c|a,c|b,c>0\)，存在 k 使得 \(km=a-b=c(a/c-b/c)\)，

上式两边除以 d 有 \(k(m/d)=(c/d)(a/c-b/c)\)，其中 \((m/d,c/d)=1\)，

根据[定理3.14]有 \(m/d|(a/c-b/c)\)，进而 \(a/c\equiv b/c\pmod{m/d}\)

或者有 \((c/d)|k\)，即 \(c/d|(a-b)/m\)，\(a/m\equiv b/m\pmod{c/d}\)（假设 \(m|a,m|b\)）

\(\blacksquare\)

假设 a，b，c，d 是整数，m 是正整数，且 \(a\equiv b\pmod m\)，\(c\equiv d\pmod m\)，则：

1. \(a+c\equiv b+d\pmod m\)
2. \(a-c\equiv b-d\pmod m\)
3. \(ac\equiv bd\pmod m\)

证明：

由 \(a\equiv b\pmod m\)，\(c\equiv d\pmod m\) 有 \(m|(a-b),m|(c-d)\)，进而存在整数 k 和 l 使得 \(km=a-b,lm=c-d\)

(1) 由 \(km=a-b,lm=c-d\) 有 \((k+l)m=(a+c)-(b+d)\)，即 \(m|((a+c)-(b+d))\)，即 \(a+c\equiv c+d\pmod m\)

(2) 由 \(km=a-b,lm=c-d\) 有 \((k-l)m=(a-c)-(b-d)\)，即 \(m|((a-c)-(b-d))\)，即 \(a-c\equiv c-d\pmod m\)

(3) 由 \(km=a-b,lm=c-d\) 有 \(ckm=c(a-b),blm=b(c-d)\)，进而 \((ck+bl)m=ac-bd\)，即 \(m|(ac-bd)\)，即 \(ac\equiv bd\pmod m\)

或者 \(ckm=c(a-b),alm=a(c-d)\)，即 \((ck-al)m=ad-bc\)，进而 \((ck-al)m|(ad-bc)\)，即 \(m|(ad-bc)\)，即 \(ad\equiv bc\pmod m\)，等价于 \(ac\equiv bd\pmod m\)

\(\blacksquare\)

m 个模 m 不同余的整数的集合构成一个模 m 的完全剩余系

反证：假设一个包含 m 个数的集合不是模 m 的完全剩余系，等价于 集合中存在两个数模 m 同余，矛盾

\(\blacksquare\)

\(\{r_1,\dots,r_m\}\) 是一个模 m 完全剩余系，那么存在正整数 a 满足 \((a,m)=1\)，使得对于任意整数 b，有：

\(\{ar_i+b~|~i=1..m\}\) 也是模 m 完全剩余系

反证：假设 \(\{ar_i+b~|~i=1..m\}\) 不是模 m 完全剩余系，即 \(\exists i\ne j,ar_i+b\equiv ar_j+b\pmod m\)

等价于 \(ar_i\equiv ar_j\pmod m\)，那么 \(r_i\equiv r_j\pmod {m/(m,a)}\)，即 \(r_i\equiv r_j\pmod {m}\)，与“\(\{r_1,\dots,r_m\}\) 是一个模 m 完全剩余系”矛盾

（其中也假设了 \((m,a)=1\)）

\(\blacksquare\)

\(a,b\) 是整数，\(k,m\) 是正整数，且 \(a\equiv b\pmod m\)，那么 \(a^k\equiv b^k\pmod m\)

证明：\(a\equiv b\pmod m\)，有 \(m|(a-b)\)，

而 \(a^k-b^k=(a-b)\sum\limits_{i=0}^{k-1}a^ib^{k-i}\)，等价于 \((a-b)|(a^k-b^k)\)，根据[定理1.8]蕴涵 \(m|(a^k-b^k)\)，

于是 \(a^k\equiv b^k\pmod m\)

\(\blacksquare\)

假设 \(a,b\in\mathbb Z\)，\(\forall i=1..k,m_k\in\mathbb N^+\)；\([m_1,\dots,m_k]\) 是 \(m_1,\dots,m_k\) 的最小公倍数

\(\forall i=1..k\)，\(a\equiv b\pmod{m_i}\)，那么 \(a\equiv b\pmod{[m_1,\dots,m_k]}\)

推论：\(\forall i=1..k\)，\(a\equiv b\pmod{m_i}\)，并且 \(\forall i\ne j,(m_i,m_j)=1\)，那么 \(a\equiv b\pmod{\prod\limits_{i=1}^km_i}\)（证明参考 3.5 习题68）

推论2：\(a\equiv b\pmod m\)，等价于 \(\forall i=1..\omega(m)\)，\(a\equiv b\pmod{p_i^{\alpha_i}}\)

证明：\(\forall i=1..k,m_i|(a-b)\to[m_1,\dots,m_k]\mid(a-b)\)：

引证：\(a|c,b|c\iff[a,b]\mid c\)；并推广：\(\forall i=1..n,a_i|c\) \(\iff\) \([a_1,\dots,a_n]\mid c\)

充分性：将 \(a,b,c\) 进行素数幂分解 \(a=\prod\limits_{i=1}^np_i^{a_i},b=\prod\limits_{i=1}^np_i^{b_i},c=\prod\limits_{i=1}^np_i^{c_i}\)

若 \(a|c,b|c\)，那么 \(\forall i=1..n\)，\(\max(a_i,b_i)\le c_i\)，因此 \([a,b]\mid c\)（其中 \([a,b]=\prod\limits_{i=1}^np_i^{\max(a_i,b_i)}\)）

必要性：由于 \(a|[a,b],b|[a,b]\)，并且 \([a,b]\mid c\)，有 \(a|c,b|c\)

推广证明：（数学归纳法的证明用到了 \([a_1,\dots,a_n]=[[a_1,\dots,a_{n-1}],a_n]\)）

\(\blacksquare\)

由 \(\forall i=1..k\)，\(a\equiv b\pmod{m_i}\) 有 \(\forall i=1..k,m_i|(a-b)\)，

当且仅当 \([m_1,\dots,m_k]\mid(a-b)\)，即 \(a\equiv b\pmod{[m_1,\dots,m_k]}\)

\(\blacksquare\)

欲求解方程 \(b^N\equiv x\pmod m\)，其中 x 是 \(b^N\) 的最小非负剩余

对 N 进行 2 次多项式分解：\(N=\sum\limits_{i=0}^{\omega_2(N)}a_i2^i\)（\(a_i=0,1\)；\(\omega_2(n)\) 指的是 n 分解后的最高次数）

于是 \(b^N=b^{\sum\limits_{i=0}^{\omega_2(N)}a_i2^i}=\prod\limits_{i=0}^{\omega_2(N)}b^{a_i2^i}=\prod\limits_{i=0}^{\omega_2(N)}(b^{2^i})^{a_i}\)

假设 \(c_i=b^{2^i}\)，有 \(c_i\cdot c_i=b^{2^i}b^{2^i}=b^{2^i+2^i}=b^{2\cdot2^i}=b^{2^{i+1}}=c_{i+1}\)

所以 \(c_{i+1}=c_i^2\) 或 \(c_i=c_{i-1}^2\)

那么 \(b^N=\prod\limits_{i=0}^{\omega_2(N)}c_i^{a_i}\)

最后 \(\prod\limits_{i=0}^{\omega_2(N)}c_i^{a_i}\equiv x\pmod m\)（\(c_i=c_{i-1}^2,c_0=b\)，\(a_i=0,1\)）

推广，对 N 做 k 次多项式分解：\(\prod\limits_{i=0}^{\omega_k(N)}c_i^{a_i}\equiv x\pmod m\)（\(c_i=c_{i-1}^k,c_0=b\)，\(a_i=0..k-1\)）

复杂度：\(O(\log_kNk\log_k^2m)\)

2. 线性同余方程

包含未知整数 x 的同余式 \(ax\equiv b\pmod m\)，称为一元线性同余方程

注：同余方程与二元线性丢番图方程是类似的

性质：若一个模 m 同余类的某个元素是某个同余方程的解，那么此同余类所有元素都是它的解

设 \(a,b\) 是整数，m 是正整数，并且 \((a,m)=d\)

1. 若 \(d\nmid b\)，那么 \(ax\equiv b\pmod m\) 无解
2. 若 \(d\mid b\)，那么 \(ax\equiv b\pmod m\) 恰有 d 个模 m 不同余的解

推论：若 \((a,m)=1\)，那么 \(ax\equiv b\pmod m\) 有模 m 的唯一解

\(ax\equiv b\pmod m\)，等价于 \(m|(ax-b)\)，即存在 y 使得 \(km=ax-b\) 或 \(b=ax-km=ax-my\)（令 \(k=y\)）

所以 \(ax\equiv b\pmod m\) 等价于二元线性丢番图方程 \(ax-my=b\)

x 是 \(ax\equiv b\pmod m\) 的解，当且仅当存在 y 使得 \(ax-my=b\)

由[定理3.23]，当 \(d|b\) 时，\(ax-my=b\) 或 \(-ax+my=-b\) 有无穷多个解：\(x=x_0+(m/d)t\)，\(y=y_0+(a/d)t\)；其中 \(x=x_0+(m/d)t\) 是线性同余方程的解，这样的解有无穷多个（但并不蕴涵这些解的同余性质）

假设 \(t_1,t_2\) 确定的两个解 \(x_1=x_0+(m/d)t_1,x_2=x_0+(m/d)t_2\) 模 m 同余，蕴涵 \(x_0+(m/d)t_1\equiv x_0+(m/d)t_2\pmod m\)

蕴涵 \((m/d)t_1\equiv (m/d)t_2\pmod m\)，蕴涵 \(t_1\equiv t_2\pmod{m/(m,m/d)}\)，蕴涵 \(t_1\equiv t_2\pmod d\)（其中 \((m,m/d)=m/d\)）

证得：若 \(x_1\equiv x_2\pmod m\)，那么 \(t_1\equiv t_2\pmod d\)

即：若 \(t_1\not\equiv t_2\pmod d\)，那么 \(x_1\not\equiv x_2\pmod m\)

当 t 取遍模 d 的完全剩余系时（特别地 \(t=0..d-1\)），可以得到 d 个模 m 不同于的解

\(\blacksquare\)

整数 a 模 m 的逆，定义为线性同余方程 \(ax\equiv1\pmod m\) 的解，记 \(x=\bar a\)

a 模 m 的逆存在，当且仅当 \((a,m)=1\)

应用：若 \((a,m)=1\)，那么 \(ax\equiv b\pmod m\)，\(\bar aax\equiv\bar ab\pmod m\)，\(x\equiv\bar ab\pmod m\)

注：可证 \(\bar a=1..p-1\)

假设 p 是素数，a 是正整数

\(a\equiv\bar a\pmod p\)，当且仅当 \(a\equiv 1\pmod p\) 或 \(a\equiv -1\pmod p\)

证明：

假设 \(p\nmid a\)，\(a\equiv\bar a\pmod p\) 等价于 \(a^2\equiv a\bar a\pmod p\)，那么 \((a,p)=1\)，那么 \(a^2\equiv1\pmod p\)，等价于 \(a\equiv 1\pmod p\) 或 \(a\equiv -1\pmod p\)

假设 \(p\mid a\)，\((a,p)=p\ge2\)，a 模 p 没有逆元

\(\blacksquare\)