线性同余

贡献者： int256

预备知识 1　同余与剩余类，最大公约数与最小公倍数

　　类比普通代数的解方程，同余式也有类似方程的问题，例如：

\begin{matrix} (1) & k a \equiv k a^{'} \overset{?}{\to} a \equiv a^{'} . \end{matrix}

显然这不一定是成立的，例如

2 \times 2 \equiv 2 \times 4 (\mod 4)

，但

2 ≢ 4 (\mod 4)

。线性同余就是讨论类似这样的问题。

定理 1　

　　若 $(k, m) = d$ ，则

\begin{matrix} (2) & k a \equiv k a^{'} (\mod m) \Leftrightarrow a \equiv a^{'} (\mod \frac{m}{d}) . \end{matrix}

　　证明：考虑 $k = k_{0} d$ 而 $m = m_{0} d$ ，则 $(k_{0}, m_{0}) = 1$ 。由

\begin{matrix} (3) & \frac{k a - k a^{'}}{m} = \frac{k_{0} (a - a^{'})}{m_{0}}, \end{matrix}

而

(k_{0}, m_{0}) = 1

，故

m | (k a - k a^{'})

当且仅当

m_{0} | (a - a^{'})

，证毕！

定理 2　

　　若 $a_{1}, a_{2}, \dots, a_{m}$ 是模 $m$ 的一个完全剩余系，且整数 $k$ 满足 $(k, m) = 1$ ，则 $k a_{1}, k a_{2}, \dots, k a_{m}$ 也是模 $m$ 的一个完全剩余系。

　　证明：对定理 1 取 $d = 1$ 时的情况，则由 $k a_{i} - k a_{j} \equiv 0 (\mod m)$ 可以得到 $a_{i} - a_{j} \equiv 0 (\mod m)$ 。而这仅当 $i = j$ 时才可能成立，故各 $k a_{i}$ 与 $k a_{j}$ 当 $i \neq j$ 时模 $m$ 不同余，而一共有 $m$ 个数，故必然构成一个 $m$ 的完全剩余系，证毕！

定理 3　

　　设 $(m_{1}, m_{2}) = 1$ ，而 $a_{1}$ 取遍模 $m_{1}$ 的一个完全剩余系， $a_{2}$ 取遍模 $m_{2}$ 的一个完全剩余系，则 $(a_{1} m_{2} + a_{2} m_{1})$ 将取遍模 $m_{1} \times m_{2}$ 的一个完全剩余系。

　　证明：由于 $a_{1}$ 有 $m_{1}$ 种取值而 $a_{2}$ 有 $m_{2}$ 种取值， $a_{1} m_{2} + a_{2} m_{1}$ 将有 $m_{1} \times m_{2}$ 种取值。考虑若存在某两对 $a_{1}, a_{2}$ 与 $a_{1}^{'}, a_{2}^{'}$ 使得

\begin{matrix} (4) & a_{1} m_{2} + a_{2} m_{1} \equiv a_{1}^{'} m_{2} + a_{2}^{'} m_{1} (\mod m_{1} m_{2}), \end{matrix}

可以考虑若

\begin{matrix} (5) & a_{1} m_{2} + a_{2} m_{1} = r (m_{1} \times m_{2}) + a_{1}^{'} m_{2} + a_{2}^{'} m_{1}, \end{matrix}

而两边同时对

m_{1}

取模，将得到

\begin{matrix} (6) & a_{1} m_{2} + a_{2} m_{1} \equiv r (m_{1} \times m_{2}) + a_{1}^{'} m_{2} + a_{2}^{'} m_{1} (\mod m_{1}), \end{matrix}

而含

m_{1}

的项在模

m_{1}

的意义下为

0

，也就是说，

\begin{matrix} (7) & a_{1} m_{2} \equiv a_{1}^{'} m_{2} (\mod m_{1}) . \end{matrix}

而由于

(m_{1}, m_{2}) = 1

，利用定理 1 可以得到

a_{1} \equiv a_{1}^{'} (\mod m_{1})

。类似的，将有

a_{2} \equiv a_{2}^{'} (\mod m_{2})

。

　　从而这 $m_{1} m_{2}$ 个数都将是两两不同余的，否则 $a_{1}$ 或 $a_{2}$ 将不取遍完全剩余系。故 $a_{1} m_{2} + a_{2} m_{1}$ 构成了模 $m_{1} \times m_{2}$ 的完全剩余系。证毕！

定理 4　定理 3 在缩系的拓展

　　若 $(m, m^{'}) = 1$ ，而 $a_{1}$ 取遍一个 $m_{1}$ 的缩系， $a_{2}$ 取遍一个 $m_{2}$ 的缩系，则 $(a_{1} m_{2} + a_{2} m_{1})$ 取遍一个 $m_{1} m_{2}$ 的缩系。

　　证明：考虑 $(a_{1} m_{2} + a_{2} m_{1}, m_{1} m_{2}) = 1$ 当且仅当 $(a_{1} m_{2} + a_{2} m_{1}, m_{1}) = 1$ 并且 $(a_{1} m_{2} + a_{2} m_{1}, m_{2}) = 1$ 。

　　而由于辗转相除（定理 2 ），则 $(a_{1} m_{2} + a_{2} m_{1}, m_{1}) = 1$ 并且 $(a_{1} m_{2} + a_{2} m_{1}, m_{2}) = 1$ 等价于说 $(a_{1} m_{2}, m_{1}) = 1$ 且 $(a_{2} m_{1}, m_{2}) = 1$ 。

　　而由于 $(m_{1}, m_{2}) = 1$ ，故这又等价于说 $(a_{1}, m_{1}) = 1$ 且 $(a_{2}, m_{2}) = 1$ 。

　　故当 $a_{1}$ 取遍 $m_{1}$ 的缩系且 $a_{2}$ 取遍 $m_{2}$ 的缩系时， $a_{1} m_{2} + a_{2} m_{1}$ 取遍 $m_{1} m_{2}$ 的缩系。证毕！

预备知识 2　整数模与裴蜀定理

定理 5　

　　若 $(k, m) = d$ ，则同余方程 $k x \equiv l (\mod m)$ 有解，当且仅当 $d | l$ 。且有解时，若考虑同余的解是相同的一组解，则其恰有 $d$ 组不同的解。

　　证明：这同余式 $k x \equiv l (\mod m)$ 等价于解 $k x - m y = l$ ，而由裴蜀定理可以知道其有解当且仅当 $d | l$ 。

　　现在，我们考虑解的个数。若 $d = 1$ ，则可以直接由刚才的定理 2 得到，仅有一组同余的解。若 $d > 1$ ，考虑有解时，则 $d | l$ ，设 $m = m_{0} d$ ， $k = k_{0} d$ ， $l = l_{0} d$ ，则此时 $(k_{0}, m_{0}) = 1$ ，且 $k x \equiv l (\mod m)$ 等价于解（直接运用刚才的定理 1 即可得到）

\begin{matrix} (8) & k_{0} x \equiv l_{0} (\mod m_{0}) . \end{matrix}

而此时

(k_{0}, m_{0}) = 1

，故这仅有一组解。考虑设这组解是

x \equiv x_{0} (\mod m_{0})

，则

\forall c \in Z

，

x = x_{0} + c m_{0}

都是解。

　　而原方程 $k x \equiv l (\mod m)$ 就是遍历所有整数 $c$ 得到的。而

\begin{matrix} (9) & x_{0} + c m_{0} \equiv x_{0} + b m_{0} (\mod m) \end{matrix}

当且仅当

m | (m_{0} (c - b))

，也就是

d | (c - b)

。从而恰有

d

组解

\begin{matrix} (10) & x_{0}, x_{0} + m_{0}, x_{0} + 2 m_{0}, \dots, x_{0} + (d - 1) m_{0} . \end{matrix}

证毕！

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。

线性同余

定理 1

定理 2

定理 3

定理 4 定理 3 在缩系的拓展

定理 5

定理 1　

定理 2　

定理 3　

定理 4　定理 3 在缩系的拓展

定理 5　