线性同余方程

在数论中，我们经常会遇到线性同余方程：

\[ ax \equiv b \pmod m \]

看起来就像把等号换成了「多一个横」的符号， 本文我们就来讨论线性同余方程。

同余

首先我们需要研究一下什么是同余。

对于整数 \(m \geq 1\)，我们定义：

\[ x \equiv y \pmod m \Leftrightarrow m \mid (x - y) \]

也就是 \(x\) 和 \(y\) 相差 \(m\) 的倍数。

这意味着，在「模 \(m\)」下， 我们关心的并不是 \(x\) 具体的数值，而是关心其属于哪一个同余类：

\[ [x] = \{ x + km \mid k \in \mathbb{Z} \} \]

因此所谓的同余方程：

\[ ax \equiv b \pmod m \]

本质是：在所有的同余类里，我们要找一个类 \([x]\) 使得 \([ax] = [b]\)。

线性同余方程

线性同余方程的标准形式是：

\[ ax \equiv b \pmod m, \ a,b \in \mathbb{Z} , m \in \mathbb{Z}_{>0} \]

我们可以把这个东西翻译成「整除」的语言：

\[ ax \equiv b \pmod m \Leftrightarrow m \mid (ax - b) \Leftrightarrow ax - b = my,\ y \in \mathbb{Z} \]

于是其等价于一个线性丢番图方程：

\[ ax - my = b \]

这个转化我认为还是比较有趣的，因为这揭示了线性同余方程就是线性丢番图方程在 \(x\) 上的投影。

如何判定有解

考虑方程：

\[ ax \equiv b \pmod m \]

我们记：

\[ g = \gcd(a,m) \]

是否有解的判定：

\[ ax \equiv b \pmod m \ 有解 \Leftrightarrow g \mid b \]

证明

根据其等价形式 \(ax - my = b\)。

根据裴蜀定理我们可以知道线性丢番图方程 \(au + mv = b\) 有解当且仅当 \(\gcd(a,m)\mid b\)。

这里的系数是 \(a\) 和 \(-m\)，\(\gcd\) 依然是 \(g\)，因此上述结论成立。

\(\text{Q.E.D.}\)

方程的转化与求解

如果 \(g \mid b\)，设：

\[ a = ga^{\prime}, \ m = gm^{\prime}, \ b = gb^{\prime} \]

那么原式就是：

\[ ga^{\prime}x \equiv gb^{\prime} \pmod {gm^{\prime}} \]

那么我们把 \(g\) 约掉：

\[ a^{\prime}x \equiv b^{\prime} \pmod {m^{\prime}} \]

此时：

\[ \gcd(a^{\prime},m^{\prime}) = 1 \]

于是我们把一般情形规约到了「系数与模数互素」的情形。

那么当 \(\gcd(a^{\prime},m^{\prime}) = 1\) 时，存在唯一的逆元 \(a^{\prime -1} \pmod {m^{\prime}}\)，使得：

\[ a^{\prime}a^{\prime -1} \equiv 1 \pmod {m^{\prime}} \]

于是：

\[ a^{\prime}x = b^{\prime} \pmod {m^{\prime}} \Rightarrow x \equiv b^{\prime} \dot a^{\prime -1} \pmod {m^{\prime}} \]

于是我们就可以求解一个模 \(m^{\prime}\) 意义下的唯一解类。

回到原方程 \(ax \equiv b \pmod m\)，假设 \(g = \gcd(a,m) \mid b\)。

我们已经得到规约方程：

\[ a^{\prime}x \equiv b^{\prime} \pmod m^{\prime}, \ \gcd(a^{\prime},m^{\prime}) = 1 \]

它在模 \(m^{\prime}\) 下有唯一解类：

\[ x \equiv x_0 \pmod {m^{\prime}} \]

解的结构分析

原方程在模 \(m\) 下恰有 \(g\) 个不同的解类，它们可以写成：

\[ x \equiv x_0 + tm^{\prime} \pmod m ,\ t = 0,1,2,\dots,g-1 \]

当然我们也可以写成：

\[ x \equiv x_0 + km^{\prime}, \ k \in \mathbb{Z} \]

这种表示「所有整数解」的形式。

但若我们关心的是「模 \(m\) 的不同解类」，那就取 \(t = 0,1,2,\dots,g-1\)，刚刚好一轮。

至于为什么是 \(g\) 个，这个其实也比较直觉。 原因就是同一个 \(x \pmod m^{\prime}\) 在模 \(m = gm^{\prime}\) 下会裂变成 \(g\) 个不同的类，相邻间隔 \(m^{\prime}\)

搞点魔怔的

如果我们搞点魔怔的，那么线性同余方程本质上就是在一个有限循环群上解方程， 答案根据「像」与「核」来决定。

模与环

我们把所有的整数按照「模 \(m\)」分成 \(m\) 类：

\[ 0,1,2,\dots,m-1 \]

并且所有的运算都发生在模 \(m\) 意义下进行，我们把这个东西当成加法群：

\[ \mathbb{Z}_m = \{[0],[1],\dots,[m-1]\} \]

我们可以将其理解成一个长度为 \(m\) 的圆环，加几就沿着环走几步。

乘是一个天然的群同态

我们定义一个函数：

\[ f: \mathbb{Z}_m \to \mathbb{Z}_m,\ f([x]) = [ax] \]

这个东西满足：

\[ f([x]+[y]) = f([x+y]) = [a(x+y)] = [ax] + [ay] = f([x]) + f([y]) \]

所以这就是一个群同态，更直观地说就是这个不破坏加法结构。

而我们要解的方程：

\[ ax \equiv b \pmod m \]

在这个语言下就可以被表述为：

\[ f([x]) = [b] \]

也就是问 \(b\) 这个点，是否在 \(f\) 的「命中范围」之内，如果在，有多少个 \(x\) 可以打到 \(b\)。

像与核

像（\(\text{image}\)）：

\[ \text{Im}(f) = \{[ax] \mid [x] \in \mathbb{Z}_m \} \]

它描述「乘 \(a\) 之后所有可能出现的结果」。 所以可解性就是：

\[ [b] \in \text{Im}(f) \]

核（\(\text{Kernel}\)）：

\[ \text{ker}(f) = \{[x] \mid [ax] = [0] \} = \{[x] \mid ax \equiv 0 \pmod m \} \]

它描述了「有哪些点会被乘 \(a\) 这个操作压到 \(0\)」。

核的大小（里面有多少个不同剩余类）会决定：一旦方程可解，会有多少个解。

为什么会这样？因为在同态里有一个非常经典的现象：

如果 \(x_0\) 是一个解（即 \(f(x_0)\) = b），那么所有的解构成一个陪集：

\[ x_0 + \text{ker}(f) \]

也就是说，解集就是「一个解 + 所有会被打成 \(0\) 的东西」。

所以在有限的情况下，解的个数 \(=\) 核的大小。

计算核

我们来数一下核：

\[ ax \equiv 0 \pmod m \Leftrightarrow m \mid ax \]

设 \(g=\gcd(a,m)\) 写：

\[ a = ga^{\prime}, \ m = gm^{\prime}, \ \gcd(a^{\prime},m^{\prime}) = 1 \]

条件 \(m \mid ax\) 变成：

\[ gm^{\prime} \mid ga^{\prime}x \Leftrightarrow m^{\prime} \mid a^{\prime}x \]

因为 \(\gcd(a^{\prime},m^{\prime}) = 1\)，所以 \(m^{\prime} \mid x\)

于是核里的 \(x\)（模 \(m\) 意义下）就是：

\[ x \equiv 0,m^{\prime},2m^{\prime},\dots,(g-1)m^{\prime} \pmod m \]

一共有 \(g\) 个不同类，因此：

\[ |\text{ker}(f)| = g = \gcd(a,m) \]

这就解释了「有解就有 \(g\) 个解」。

这并非巧合，是核的大小决定了每个被命中的点有多少个原像。

于是像的大小也随之确定

有限群同态满足一个「计数恒等式」（可以理解成「每个能被命中的点都有同样多的原像」）：

\[ |\mathbb{Z}_m| = |\text{ker}(f)| \times |\text{Im}(f)| \]

这里 \(|\mathbb{Z}_m| , |\text{ker}(f)| = g\)，所以：

\[ |\text{Im}(f)| = \frac{m}{g} \]

也就是说：乘 \(a\) 在模 \(m\) 下最多只会打到 \(\frac{m}{g}\) 个不同的结果。

当 \(g > 1\) 的时候，它会「压扁」空间，让很多不同的 \(x\) 映射到同一个值上。

可解性

最后我们把 \([b] \in \text{Im}(f)\) 翻译回整除语言。

注意：像里的任何元素都形如 \([ax]\)，那么它们和 \(g\) 的关系是：

• 因为 \(g \mid a\) 且 \(g \mid m\) 所以 \(ax\) 在模 \(m\) 意义下的代表数一定满足与 \(g\) 一致的整除结构。

• 标准结论就是：

\[ [b] \in \text{Im}(f) \Leftrightarrow g \mid b \]

于是：

• \(g \nmid b\)：\(b\) 根本不在像里，打不到自然无解。
• \(g \mid b\)：\(b\) 在像里，能打到所以有解，并且所有原像大小为 \(|ker| = g\)。

这样一来我们就把三个事情统一起来了：

• \(ax \equiv b \pmod m\) 有解
• \(\gcd(a,m) \mid b\)
• 若有解，解类数 \(= \gcd(a,m)\)

所有解的样子

因为解集为一个解 \(+\) 核，而核是：

\[ \{0,m^{\prime},2m^{\prime},\dots,(g-1)m^{\prime}\} (m^{\prime} = \frac{m}{g}) \]

所以一旦我们找到一个解 \(x_0\)，所有解就是：

\[ x \equiv x_0 + t \times \frac{m}{g} \pmod m, \ t = 0,1,2,\dots,g-1 \]

这就是我们熟悉的公式，但现在它不是我们记住的，而是从「核」与「陪集」中自然发现出来的。

日志

本页面创建于 2025/12/20 17:40

为了写完我晚下班了十分钟。

UPD-1：2025/12/23 09:37

修正若干 \(\text{typo}\) 和格式错误。