贡献者： int256
预备知识 1 同余与剩余类
，
最大公约数与最小公倍数
类比普通代数的解方程，同余式也有类似方程的问题，例如：
\begin{equation}
ka \equiv ka' \xrightarrow{?} a \equiv a' ~.
\end{equation}
显然这不一定是成立的，例如 $2 \times 2 \equiv 2 \times 4 \pmod 4$，但 $2 \not \equiv 4 \pmod 4$。线性同余就是讨论类似这样的问题。
定理 1
若 $(k, m) = d$，则
\begin{equation}
ka \equiv ka' \pmod m \Leftrightarrow a \equiv a' \pmod{\frac{m}{d}} ~.
\end{equation}
证明：考虑 $k = k_0 d$ 而 $m = m_0 d$，则 $(k_0, m_0) = 1$。由
\begin{equation}
\frac{ka - ka'}{m} = \frac{k_0(a - a')}{m_0} ~,
\end{equation}
而 $(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$，则 $ka_1, ka_2, \dots, ka_m$ 也是模 $m$ 的一个完全剩余系。
证明：对定理 1 取 $d=1$ 时的情况，则由 $ka_i - ka_j \equiv 0 \pmod m$ 可以得到 $a_i - a_j \equiv 0 \pmod m$。而这仅当 $i = j$ 时才可能成立，故各 $ka_i$ 与 $ka_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_1m_2+a_2m_1$ 将有 $m_1 \times m_2$ 种取值。考虑若存在某两对 $a_1, a_2$ 与 $a_1', a_2'$ 使得
\begin{equation}
a_1 m_2 + a_2 m_1 \equiv a_1' m_2+ a_2' m_1 \pmod{m_1 m_2} ~,
\end{equation}
可以考虑若
\begin{equation}
a_1 m_2 + a_2 m_1= r(m_1 \times m_2) + a_1' m_2 + a_2' m_1 ~,
\end{equation}
而两边同时对 $m_1$ 取模，将得到
\begin{equation}
a_1 m_2 + a_2 m_1 \equiv r(m_1 \times m_2) + a_1' m_2 + a_2' m_1 \pmod{m_1} ~,
\end{equation}
而含 $m_1$ 的项在模 $m_1$ 的意义下为 $0$，也就是说，
\begin{equation}
a_1 m_2 \equiv a_1' m_2 \pmod{m_1} ~.
\end{equation}
而由于 $(m_1, m_2) = 1$，利用
定理 1 可以得到 $a_1 \equiv a_1' \pmod{m_1}$。类似的，将有 $a_2 \equiv a_2' \pmod{m_2}$。
从而这 $m_1m_2$ 个数都将是两两不同余的，否则 $a_1$ 或 $a_2$ 将不取遍完全剩余系。故 $a_1m_2+a_2m_1$ 构成了模 $m_1\times m_2$ 的完全剩余系。证毕！
定理 4 定理 3 在缩系的拓展
若 $(m, m') = 1$，而 $a_1$ 取遍一个 $m_1$ 的缩系，$a_2$ 取遍一个 $m_2$ 的缩系，则 $(a_1m_2 + a_2 m_1)$ 取遍一个 $m_1m_2$ 的缩系。
证明：考虑 $(a_1m_2 + a_2m_1, m_1m_2) = 1$ 当且仅当 $(a_1m_2 + a_2m_1, m_1) = 1$ 并且 $(a_1m_2 + a_2m_1, m_2) = 1$。
而由于辗转相除（定理 2 ），则 $(a_1m_2 + a_2m_1, m_1) = 1$ 并且 $(a_1m_2 + a_2m_1, m_2) = 1$ 等价于说 $(a_1m_2, m_1) = 1$ 且 $(a_2m_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_1m_2+a_2m_1$ 取遍 $m_1m_2$ 的缩系。证毕！
定理 5
若 $(k, m) = d$，则同余方程 $kx \equiv l \pmod m$ 有解，当且仅当 $d | l$。且有解时，若考虑同余的解是相同的一组解，则其恰有 $d$ 组不同的解。
证明：这同余式 $kx \equiv l \pmod m$ 等价于解 $kx - my = 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$，且 $kx \equiv l \pmod m$ 等价于解（直接运用刚才的定理 1 即可得到）
\begin{equation}
k_0 x \equiv l_0 \pmod {m_0} ~.
\end{equation}
而此时 $(k_0, m_0) = 1$，故这仅有一组解。考虑设这组解是 $x \equiv x_0 \pmod {m_0}$，则 $\forall c \in \mathbb Z$，$x = x_0 + c m_0$ 都是解。
而原方程 $kx \equiv l \pmod m$ 就是遍历所有整数 $c$ 得到的。而
\begin{equation}
x_0 + c m_0 \equiv x_0 + b m_0 \pmod m ~~
\end{equation}
当且仅当 $m | (m_0 (c - b))$，也就是 $d | (c - b)$。从而恰有 $d$ 组解
\begin{equation}
x_0, x_0 + m_0, x_0 + 2 m_0, \dots, x_0 + (d-1) m_0 ~.
\end{equation}
证毕！
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。