5.4.3 同余和剩余类

1. 同余

设 $m$ 是正整数, $m>1$ . 如果当除以 $m$ 时两个整数 $a$ 和 $b$ 有相同的余数,那么 $a$ 和 $b$ 称为模 $m$ 同余,并记作 $a\equiv b\mathrm{mod}m$ 或 $a\equiv b\left(m\right)$ .

$3\equiv 13\mathrm{mod}5,38\equiv 13\mathrm{mod}5,3\equiv -2\mathrm{mod}5.$

注 显然, $a\equiv b\mathrm{mod}m$ 成立,当且仅当 $m$ 是差 $a-b$ 的因子. 模 $m$ 同余是整数集合间的等价关系 (参见第 447 页 5.2.4, 1.). 注意下列性质:

$$\begin{array}{}\text{(5.244a)}& a\equiv a\mathrm{mod}m,\text{ 对每个 }a\in \mathbb{Z},\end{array}$$$$\begin{array}{}\text{(5.244b)}& a\equiv b\mathrm{mod}m\Rightarrow b\equiv a\mathrm{mod}m,\end{array}$$$$\begin{array}{}\text{(5.244c)}& a\equiv b\mathrm{mod}m\wedge b\equiv c\mathrm{mod}m\Rightarrow a\equiv c\mathrm{mod}m.\end{array}$$

2. 计算法则

$$\begin{array}{}\text{(5.245a)}& a\equiv b\mathrm{mod}m\wedge c\equiv d\mathrm{mod}m\Rightarrow a+c\equiv b+d\mathrm{mod}m,\end{array}$$$$\begin{array}{}\text{(5.245b)}& a\equiv b\mathrm{mod}m\wedge c\equiv d\mathrm{mod}m\Rightarrow a\cdot c\equiv b\cdot d\mathrm{mod}m,\end{array}$$$$\begin{array}{}\text{(5.245c)}& a\cdot c\equiv b\cdot c\mathrm{mod}m\wedge gcd\left(c,m\right)=1\Rightarrow a\equiv b\mathrm{mod}m,\end{array}$$$$\begin{array}{}\text{(5.245d)}& a\cdot c\equiv b\cdot c\mathrm{mod}m\wedge c\ne 0\Rightarrow a\equiv b\mathrm{mod}\frac{m}{gcd\left(c,m\right)}.\end{array}$$

3. 剩余类、剩余类环

因为模 $m$ 同余是 $\mathbb{Z}$ 中的等价关系,所以这个关系导致将 $\mathbb{Z}$ 分拆为模 $m$ 剩余类:

$$\begin{array}{}\text{(5.246)}& {\left[a\right]}_m=\{x\mid x\in \mathbb{Z}\wedge x\equiv a\mathrm{mod}m\}.\end{array}$$

剩余类 “ $a$ 模 $m$ ” 由所有用 $m$ 除时有相等的余数的整数组成. 于是当且仅当 $a\equiv$ $b\mathrm{mod}m$ 时 ${\left[a\right]}_m={\left[b\right]}_m$ .

恰有 $m$ 个模 $m$ 剩余类,并且通常用它们的最小非负代表元表示:

$$\begin{array}{}\text{(5.247)}& {\left[0\right]}_m,{\left[1\right]}_m,\cdots ,{[m-1]}_m.\end{array}$$

在模 $m$ 剩余类的集合 ${\mathbb{Z}}_m$ 中,剩余类加法和剩余类乘法定义为

$$\begin{array}{}\text{(5.248)}& {\left[a\right]}_m\oplus {\left[b\right]}_m={[a+b]}_m,\end{array}$$$$\begin{array}{}\text{(5.249)}& {\left[a\right]}_m\otimes {\left[b\right]}_m={[a\cdot b]}_m.\end{array}$$

这些剩余类运算与代表元的选取无关,即 ${\left[a\right]}_m={\left[a^{\prime }\right]}_m$ 和 ${\left[b\right]}_m={\left[b^{\prime }\right]}_m$ 蕴涵

$$\begin{array}{}\text{(5.250)}& {\left[a\right]}_m\oplus {\left[b\right]}_m={\left[a^{\prime }\right]}_m\oplus {\left[b^{\prime }\right]}_m\text{ 及 }{\left[a\right]}_m\otimes {\left[b\right]}_m={\left[a^{\prime }\right]}_m\otimes {\left[b^{\prime }\right]}_m.\end{array}$$

模 $m$ 剩余类关于剩余类加法和剩余类乘法形成一个有单位元的环 (参见第 504 页 5.4.3,1.),即模 $m$ 剩余类环. 如果 $p$ 是一个素数,那么模 $p$ 剩余类环是一个域 (参见第 484 页5.3.7.1,2.).

4. 与 $m$ 互素的剩余类

满足 $gcd\left(a,m\right)=1$ 的剩余类称为与 $m$ 互素的剩余类. 如果 $p$ 是素数,那么所有不等于 ${\left[0\right]}_p$ 的剩余类与 $p$ 互素.

与 $m$ 互素的剩余类对于剩余类乘法形成一个阿贝尔群 (参见第 451 页 5.3.3.1, 1.),称作与 $m$ 互素的剩余类群. 这个群的阶是 $\phi \left(m\right)$ ,这里 $\phi$ 是欧拉函数 (参见第 509 页 5.4.4, 1.).

$◼\mathbf{A}$: ${\left[1\right]}_8,{\left[3\right]}_8,{\left[5\right]}_8,{\left[7\right]}_8$ 是与 8 互素的剩余类.

$◼\mathbf{B}$: ${\left[1\right]}_5,{\left[2\right]}_5,{\left[3\right]}_5,{\left[4\right]}_5$ 是与 5 互素的剩余类.

$◼\mathbf{C}$: 有 $\phi \left(8\right)=\phi \left(5\right)=4$ .

5. 本原剩余类

一个与 $m$ 互素的剩余类 ${\left[a\right]}_m$ 称作本原剩余类,如果它在与 $m$ 互素的剩余类群中有阶 $\phi \left(m\right)$ .

$◼\mathbf{A}$: ${\left[2\right]}_5$ 是模 5 本原剩余类,因为 ${\left({\left[2\right]}_5\right)}^2={\left[4\right]}_5,{\left({\left[2\right]}_5\right)}^3={\left[3\right]}_5,{\left({\left[2\right]}_5\right)}^4={\left[1\right]}_5$ .

$◼\mathbf{B}$: 因为在与 8 互素的剩余类群中 ${\left[1\right]}_8$ 有阶 1,并且 ${\left[3\right]}_8,{\left[5\right]}_8,{\left[7\right]}_8$ 有阶 2,所以存在模 $m$ 非本原剩余类.

注 当且仅当 $m=3,m=4,m=p^k$ 或 $m=2p^k$ (其中 $p$ 是奇素数,而 $k$ 是正整数) 时,存在模 $m$ 本原剩余类.

如果存在模 $m$ 本原剩余类,那么与 $m$ 互素的剩余类群形成循环群.

6. 线性同余式

(1)定义 如果 $a,b$ 和 $m>0$ 是整数,那么

$$\begin{array}{}\text{(5.251)}& ax\equiv b\left(m\right)\end{array}$$

称为(未知数 $x$ 的) 线性同余式.

(2) 解 满足 $a{x}^{\ast }\equiv b\left(m\right)$ 的整数 $x^{\ast }$ 是这个同余式的一个解. 每个模 $m$ 同余 $x^{\ast }$ 的整数也是一个解. 为求 (5.259) 的所有解,只需求模 $m$ 两两互不同余且满足同余式的整数.

同余式 (5.251) 可解,当且仅当 $gcd\left(a,m\right)$ 是 $b$ 的因子. 此时,模 $m$ 解数等于 $gcd\left(a,m\right)$ .

特别地,如果 $gcd\left(a,m\right)=1$ ,那么同余式模 $m$ 有唯一解.

(3) 解法 线性同余式有不同的解法. 可将同余式 $ax\equiv b\left(m\right)$ 转换为丢番图方程 $ax+my=b$ ,并且确定丢番图方程 $a^{\prime }x+m^{\prime }y=b^{\prime }$ 的一个特解 $\left(x^0,y^0\right)$ ,此处 $a^{\prime }=a/gcd\left(a,m\right),m^{\prime }=m/gcd\left(a,m\right),b^{\prime }=b/gcd\left(a,m\right)$ (参见第 502 页 5.4.2,1.).

因为 $gcd\left(a,m\right)=1$ ,所以同余式 $a^{\prime }x\equiv b^{\prime }\left(m^{\prime }\right)$ 模 $m^{\prime }$ 有唯一解,并且

$$\begin{array}{}\text{(5.252a)}& x\equiv x^0\left(m^{\prime }\right).\end{array}$$

同余式 $ax\equiv b\left(m\right)$ 模 $m$ 恰有 $gcd\left(a,m\right)$ 个解:

$$\begin{array}{}\text{(5.252b)}& x^0,x^0+m,x^0+2m,\cdots ,x^0+\left(gcd\left(a,m\right)-1\right)m.\end{array}$$

因为 $gcd\left(114,315\right)$ 是 6 的因子,所以 $114x\equiv 6\mathrm{mod}315$ 可解; 模 315 有 3 个解.

$38x\equiv 2\mathrm{mod}105$ 有唯一解: $x\equiv 94\mathrm{mod}105$ (参见第 503 页 5.4.2,4.). 94,199 和 304 是 $114x\equiv 6\mathrm{mod}315$ 的解.

7. 联立线性同余式

如果给定有限多个同余式

$$\begin{array}{}\text{(5.253)}& x\equiv b_1\left(m_1\right),x\equiv b_2\left(m_2\right),\cdots ,x\equiv b_t\left(m_t\right),\end{array}$$

那么 (5.253) 称作联立线性同余式组. 关于解集的一个结果是中国剩余定理: 考虑给定的同余式组 $x\equiv b_1\left(m_1\right),x\equiv b_2\left(m_2\right),\cdots ,x\equiv b_t\left(m_t\right)$ ,其中 $m_1,m_2,\cdots ,m_t$ 是两两互素的整数. 如果

$$\begin{array}{}\text{(5.254a)}& m=m_1\cdot m_2\cdots m_t,a_1=\frac{m}{m_1},a_2=\frac{m}{m_2},\cdots ,a_t=\frac{m}{m_t},\end{array}$$

并且选取 $x_j$ 使得 $a_j{x}_j\equiv b_j\left(m_j\right)\left(j=1,2,\cdots ,t\right)$ ,那么

$$\begin{array}{}\text{(5.254b)}& x^{\prime }=a_1{x}_1+a_2{x}_2+\cdots +a_t{x}_t\end{array}$$

是同余式组的一个解. 同余式组模 $m$ 有唯一解,即如果 $x^{\prime }$ 一个解,那么当且仅当 $x^{\prime \prime }\equiv x^{\prime }\mathrm{mod}m$ 时 $x^{\prime \prime }$ 也是一个解.

解同余式组 $x\equiv 1\left(2\right),x\equiv 2\left(3\right),x\equiv 4\left(5\right)$ ,这里整数2,3,5两两互素. 于是 $m=$ $30,a_1=15,a_2=10,a_3=6$ . 同余式 $15x_1\equiv 1\left(2\right),10x_2\equiv 2\left(3\right),6x_3\equiv 4\left(5\right)$ 有特解 $x_1=1,x_2=2,x_3=4$ . 给定的同余式组模 $m$ 有唯一解 $x\equiv 15\cdot 1+10\cdot 2+6\cdot 4\left(30\right)$ , 即 $x\equiv 29\left(30\right)$ .

注 应用联立线性同余式组可以将解模 $m$ 非线性同余式的问题归结为解模素数幂同余式的问题 (参见第 508 页 5.4.3, 9.).

8. 二次同余式

(1) 模 $\mathbf{m}$ 二次剩余 如果我们能解每个同余式 $x^2\equiv a\left(m\right)$ ,那么就能解每个同余式 $a{x}^2+bx+c\equiv 0\left(m\right)$ :

$$\begin{array}{}\text{(5.255)}& a{x}^2+bx+c\equiv 0\left(m\right)\iff {(2ax+b)}^2\equiv b^2-4ac\left(m\right).\end{array}$$

首先考虑模 $m$ 二次剩余: 设 $m\in \mathbb{N},m>1$ ,以及 $a\in \mathbb{Z}$ 并且 $gcd\left(a,m\right)=1$ . 数 $a$ 称为模 $m$ 二次剩余,当且仅当存在 $a\in \mathbb{Z}$ 使得 $x^2\equiv a\left(m\right)$ .

如果给定 $m$ 的标准素因子分解式,即

$$\begin{array}{}\text{(5.256)}& m=\prod _{i=1}^{\mathrm{\infty }}{p}_i^{{\alpha }_i}\end{array}$$

那么 $r$ 是模 $m$ 二次剩余,当且仅当 $r$ 对于 $i=1,2,3,\cdots$ 是模 $p_i^{{\alpha }_i}$ 二次剩余.

如果 $a$ 是模素数 $p$ 二次剩余,那么将此记作 $\left(\frac{a}{p}\right)=1$ ; 如果 $a$ 是模 $p$ 二次非剩余,那么记作 $\left(\frac{a}{p}\right)=-1$ (勒让德符号).

数1,4,7是模 9 二次剩余.

(2) 二次同余的性质

(E1) $p\nmid ab$ 及 $a\equiv b\left(p\right)$ 蕴涵 $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$ .(5.257a)

(E2) $\left(\frac{1}{p}\right)=1$ .(5.257b)

(E3) $\left(\frac{-1}{p}\right)={(-1)}^{\frac{p-1}{2}}$ .(5.257c)

(E4) $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ ,特别, $\left(\frac{a{b}^2}{p}\right)=\left(\frac{a}{p}\right)$ .(5.257d)

(E5) $\left(\frac{2}{p}\right)={(-1)}^{\frac{p^2-1}{8}}$ .(5.257e)

(E6) 二次互反律: 如果 $p$ 和 $q$ 是不同的奇素数,那么

$$\begin{array}{}\text{(5.257f)}& \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)={(-1)}^{\frac{p-1}{2}\frac{q-1}{2}}.\end{array}$$

$◼$ $\left(\frac{65}{307}\right)=\left(\frac{5}{307}\right)\cdot \left(\frac{13}{307}\right)=\left(\frac{2}{5}\right)\cdot \left(\frac{8}{13}\right)={(-1)}^{\frac{5^2-1}{8}}\left(\frac{2^3}{13}\right)=-\left(\frac{2}{13}\right)=$ $-{(-1)}^{\frac{{13}^2-1}{8}}=1$ .

一般地 同余式 $x^2\equiv a\left(2^{\alpha }\right),gcd\left(a,2\right)=1$ 可解,当且仅当 $a\equiv 1\left(4\right)$ (若 $\alpha =2$ ) 以及 $a\equiv 1\left(8\right)$ (若 $\alpha \ge 3$ ). 如果这些条件被满足,那么模 $2^{\alpha }$ 有一个解 (若 $\alpha =1$ ), 有两个解 (若 $\alpha =2$ ),以及有四个解 (若 $\alpha \ge 3$ ).

一般形式的同余式

$$\begin{array}{}\text{(5.258a)}& x^2\equiv a\left(m\right),m=2^{\alpha }{p}_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_t^{{\alpha }_t},gcd\left(a,m\right)=1,\end{array}$$

可解性的必要条件是同余式

$$a\equiv 1\left(4\right)\text{(当}\alpha =2\text{),}a\equiv 1\left(8\right)\text{(当}\alpha \ge 3\text{),}\left(\frac{a}{p_1}\right)=1,\left(\frac{a}{p_2}\right)=1,\cdots ,\left(\frac{a}{p_t}\right)=1$$

(5.258b)

的可解性. 如果所有这些条件被满足,那么解数等于 $2^t$ (当 $\alpha =0$ 和 $\alpha =1$ ),等于 $2^{t+1}$ (当 $\alpha =2$ ),以及等于 $2^{t+2}$ (当 $\alpha \ge 3$ ).

9. 多项式同余

如果整数 $m_1,m_2,\cdots ,m_t$ 两两互素,那么同余式

$$\begin{array}{}\text{(5.259a)}& f\left(x\right)\equiv a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_0\equiv 0\left(m_1{m}_2\cdots m_t\right)\end{array}$$

等价于同余式组

$$\begin{array}{}\text{(5.259b)}& f\left(x\right)\equiv 0\left(m_1\right),f\left(x\right)\equiv 0\left(m_2\right),\cdots ,f\left(x\right)\equiv 0\left(m_t\right).\end{array}$$

如果对于 $j=1,2,\cdots ,t,f\left(x\right)\equiv 0\left(m_j\right)$ 的解数是 $k_j$ ,那么 $f\left(x\right)\equiv 0\left(m_1{m}_2\cdots m_t\right)$ 的解数是 $k_1{k}_2\cdots k_t$ . 这意味着同余式

$$\begin{array}{}\text{(5.259c)}& f\left(x\right)\equiv 0\left(p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_t^{{\alpha }_t}\right)\end{array}$$

(其中 $p_1,p_2,\cdots ,p_t$ 是素数) 的解可以归结为 $f\left(x\right)\equiv 0\left(p^{\alpha }\right)$ 的解. 此外,这些同余式可以用下列方式归结为模素数的同余式 $f\left(x\right)\equiv 0\left(p\right)$ :

**a) $f(\ast \ast x)\equiv 0\left(p^{\alpha }\right)$ 的解也是 $f\left(x\right)\equiv 0\left(p\right)$ 的解.

b) 当且仅当 $p$ 不整除 $f^{\prime }\left(x_1\right)$ 时, $f\left(x\right)\equiv 0\left(p\right)$ 的解 $x\equiv x_1\left(p\right)$ 由模 $p^{\alpha }$ 的解唯一确定:

设 $f\left(x_1\right)\equiv 0\left(p\right)$ . 令 $x=x_1+p{t}_1$ ,并且确定线性同余式

$$\begin{array}{}\text{(5.260a)}& \frac{f\left(x_1\right)}{p}+f^{\prime }\left(x_1\right)t_1\equiv 0\left(p\right)\end{array}$$

的唯一解 $t_1^{\prime }$ . 将 $t_1=t_1^{\prime }+p{t}_2$ 代入 $x=x_1+p{t}_1$ ,那么得到 $x=x_2+p^2{t}_2$ . 现在要确定线性同余式

$$\begin{array}{}\text{(5.260b)}& \frac{f\left(x_2\right)}{p^2}+f^{\prime }\left(x_2\right)t_2\equiv 0\left(p\right)\end{array}$$

的模 $p^2$ 解 $t_2^{\prime }$ . 将 $t_2=t_2^{\prime }+p{t}_3$ 代入 $x=x_2+p^2{t}_2$ ,得到结果 $x=x_3+p^3{t}_3$ . 继续这个过程产生 $f\left(x\right)\equiv 0\left(p^{\alpha }\right)$ 的解.

解同余式 $f\left(x\right)=x^4+7x+4\equiv 0\left(27\right).f\left(x\right)=x^4+7x+4\equiv 0\left(3\right)$ 蕴涵 $x\equiv 1\left(3\right)$ ,即 $x=1+3t_1$ . 因为 $f^{\prime }\left(x\right)=4x^3+7$ ,并且 $3\nmid f^{\prime }\left(1\right)$ ,现在来求同余式 $f\left(1\right)/3+f^{\prime }\left(1\right)\cdot t_1\equiv 4+11t_1\equiv 0\left(3\right)$ 的解: $t_1\equiv 1\left(3\right)$ ,即 $t_1=1+3t_2$ ,以及 $x=4+9t_2$ . 然后考虑 $f\left(4\right)/9+f^{\prime }\left(4\right)\cdot t_2\equiv 0\left(3\right)$ ,并且得到解 $t_2\equiv 2\left(3\right)$ ,即 $t_2=2+3t_3$ ,以及 $x=22+27t_3$ . 因此 22 是 $x^4+7x+4\equiv 0\left(27\right)$ 的解,并且模 27 唯一确定.