目录

浅谈线性同余及中国剩余定理

目录

我记得在计算机复赛前一天晚上本想看看同余方程的解法,结果第二天就考到了。明天是数学竞赛初赛,简略的复习一下线性同余及中国剩余定理,顺便记下一些笔记。

定理1:令 $m$ 为正整数。若 $\begin{cases} a \equiv b \pmod m \\ c \equiv d \pmod m \end{cases}$,那么 $\begin{cases} a+c \equiv b+d \pmod m \\ ac \equiv bd \pmod m\end{cases}$。

证明:因为 $\begin{cases} a \equiv b \pmod m \\ c \equiv d \pmod m\end{cases}$,所以有整数 $s$ 和 $t$ 使 $\begin{cases} b=a+sm \\ d=c+tm\end{cases}$。于是 $$ \begin{cases} b+d=(a+sm)+(c+tm)=(a+c)+m(s+t)\\ bd=(a+sm)(c+tm)=ac+m(at+cs+stm) \end{cases} \Rightarrow \begin{cases} a+c \equiv b+d \pmod m \\ ac \equiv bd \pmod m \end{cases}$$

:由于 $\begin{cases} 7 \equiv 2 \pmod 5 \\ 11 \equiv 1 \pmod 5\end{cases}$,从定理1知 $\begin{cases} 18 = 7+11 \equiv 2+1=3 \pmod 5 \\ 77 = 7 \cdot 11 \equiv 2 \cdot 1=2 \pmod 5\end{cases}$。

定理2:如果 $a$ 和 $m$ 为互素的整数,$m > 1$,则存在 $a$ 的模 $m$ 的逆。而且这个逆模 $m$ 是唯一的。(即有小于 $m$ 的唯一正整数 $\overline{a}$,如果这样的 $\overline{a}$ 存在的话。这样的 $\overline{a}$ 称为 $a$ 模 $m$ 逆,且 $a$ 的任何别的模 $m$ 逆均和 $\overline{a}$ 模 $m$ 同余。)

证明:由定理 1 及 $\gcd \left ( a,m \right )=1$ 知,有整数 $s$ 和 $t$ 使 $$sa+tm=1$$ 于是 $$sa+tm \equiv 1 \pmod m$$ 由于 $tm \equiv 0 \pmod m$,所以 $$sa \equiv 1 \pmod m$$ 结论是 $s$ 为 $a$ 的模 $m$ 逆。

:求 $3$ 的模 $7$ 逆。

:由于 $\gcd \left ( 3,7 \right )=1$,定理 3 说明存在 $3$ 模 $7$ 的逆。若用欧几里得算法求 $3$ 和 $7$ 的最大公约数,算法很快结束:$$7=2 \cdot 3 + 1$$ 从这一等式看到 $$-2 \cdot 3 + 1 \cdot 7=1$$ 这说明 -2 是 3 模 7 的一个逆。(注意,模 $7$ 同余于 $-2$ 的每个整数也是 $3$ 的逆,例如 $5,-9,12$ 等。)

:求线性同余 $3x \equiv 4 \pmod 7$ 的解。

:易知 $-2$ 是 $3$ 模 $7$ 的逆。在同余式的两边同乘以 $-2$ 得 $$-2 \cdot 3x \equiv -2 \cdot 4 \pmod 7$$ 因为 $\begin{cases} -6 \equiv 1 \pmod 7 \\ -8 \equiv 6 \pmod 7\end{cases}$,所以若 $x$ 是解,必有 $$x \equiv -8 \equiv 6 \pmod 7$$ 于是由定理 1,有 $$3x \equiv 3 \cdot 6 \equiv 18 \equiv 4 \pmod 7 $$ 这说明所有这种 $x$ 满足问题中的同余式。结论是,同余方程的解是使 $x \equiv 6 \pmod 7$ 的整数。

从有关线性同余系统的中国古典问题而得名的中国剩余定理,可以这样叙述:只要线性同余系统的模数两两互素,则该系统有解,而且以所有模数之乘积取模,解是唯一的。

定理3(中国剩余定理):令 $m_{1},m_{2},\cdots,m_{n}$ 为两两互素的正整数,则同余方程组 $$ \begin{cases} x \equiv a_{1} \pmod {m_{1}}\\ x \equiv a_{2} \pmod {m_{2}}\\ \vdots \\ x \equiv a_{1} \pmod {m_{n}} \end{cases}$$ 唯一的模 $m=m_{1}m_{2} \cdots m_{n}$ 解。(即有一个解 $x$,使 $0 \leq x \leq m$,且所有其他的解均与此解模 $m$ 同余。)

证明:要建立这一定理,需要证明有一个解存在,而且是模 $m$ 唯一的。下面将给出构造这样一个解的方法以证明解的存在。

要构造一个适合各方程的解,首先对 $k=1,2, \cdots ,n$,令 $M_{k}=\frac{m}{m_{k}}$,即 $M_{k}$ 是除 $m_{k}$ 以外所有模数的乘积。由于 $i \neq k$ 时,$m_{i}$ 和 $m_{k}$ 没有大于 1 的公因子,所以 $\gcd \left ( m_{k},M_{k} \right )=1$。从而由定理 2 知有整数 $y_{k}$,即 $M_{k}$ 模 $m_{k}$ 的逆,使得 $$M_{k}y_{k} \equiv 1 \pmod {m_{k}}$$ 要得到适合所有方程的解,令 $$x=a_{1}M_{1}y_{1}+a_{2}M_{2}y_{2}+\cdots+a_{n}M_{n}y_{n}$$ 现要证明 $x$ 就是这样一个解。

首先注意,由于只要 $j \neq k$,就有 $M_{j} \equiv 0 \pmod {m_{k}}$,在 $x$ 的求和表达式中除第 $k$ 项以外的各项模 $m_{k}$ 均同余于 $0$。由于 $M_{k}y_{k} \equiv 1 \pmod {m_{k}}$,可以看出对 $k=1,2, \cdots ,n$,均有 $$x \equiv a_{n}M_{n}y_{n} \equiv a_{k} \pmod {m_{k}}$$。这就证明了 $x$ 是这 $n$ 个同余方程的公共解。

:求同余方程组 $\begin{cases} x \equiv 2 \pmod 3\\ x \equiv 3 \pmod 5\\ x \equiv 2 \pmod 7 \end{cases}$ 的解。

:首先令 $m=3 \cdot 5 \cdot 7=105$,$M_{1}=\frac {m} {3}=35$,$M_{2}=\frac {m} {5}=21$,$M_{3}=\frac {m} {7}=15$。可看到 $2$ 是 $M_{1}=35$ 的模 $3$ 逆,因为 $35 \equiv 2 \pmod 3$;$1$ 是 $M_{2}=21$ 的模 $5$ 逆,因为 $21 \equiv 1 \pmod 5$;$1$ 也是 $M_{3}=15$ 的模 $7$ 逆,因为 $15 \equiv -1 \pmod 4$。于是这一方程组的解是满足下列式子的那些 $x$: $$ x \equiv a_{1}M_{1}y_{1}+a_{2}M_{2}y_{2}+a_{3}M_{3}y_{3}=2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1=233 \equiv 23 \pmod {105} $$

可以见 $23$ 是所有解当中最小的正整数。结论是 $23$ 是最小的正整数,除以 $3$ 时余 $2$,除以 $5$ 时余 $3$,除以 $7$ 时余 $2$。