线性同余方程
本文讨论线性同余方程的求解．
基本概念
设 𝑎,𝑏,𝑛a,b,n
为整数，𝑥x 为未知数，那么，形如
𝑎𝑥≡𝑏(mod𝑛)ax≡b(modn)
的方程称为 线性同余方程 （linear congruence equation）．
求解线性同余方程，需要找到区间 [0,𝑛 −1][0,n−1] 中 𝑥x 的全部解．当然，将它们加减 𝑛n 的任意倍数，依然是方程的解．在模 𝑛n 的意义下，这些就是该方程的全部解．
本文接下来介绍了两种求解线性同余方程的思路，分别利用了逆元和不定方程．对于一般的情形，逆元和不定方程的求解都需要用到 扩展欧几里得算法，因此，这两种思路其实是一致的．
用逆元求解
首先，考虑 𝑎a 和 𝑛n 互素的情形，即 gcd(𝑎,𝑛) =1gcd(a,n)=1 的情形．此时，可以计算 𝑎a 的 逆元 𝑎−1a−1，并将方程两边同乘以 𝑎−1a−1，这就得到方程的唯一解：
𝑥≡𝑏𝑎−1(mod𝑛).x≡ba−1(modn).
紧接着，考虑 𝑎a 和 𝑛n 不互素的情形，即 gcd(𝑎,𝑛) =𝑑 >1gcd(a,n)=d>1 的情形．此时，原方程不一定有解．例如，2𝑥 ≡1(mod4)2x≡1(mod4) 就没有解．因此，需要考虑两种情形：
- 当 𝑑d 不能整除 𝑏b 时，方程无解．对于任意的 𝑥x，方程左侧 𝑎𝑥ax 都是 𝑑d 的倍数，但是方程右侧 𝑏b 不是 𝑑d 的倍数．因此，它们不可能相差 𝑛n 的倍数，因为 𝑛n 的倍数也一定是 𝑑d 的倍数．因此，方程无解．
- 当 𝑑d 可以整除 𝑏b 时，可以将方程的参数 𝑎,𝑏,𝑛a,b,n 都同除以 𝑑d，得到一个新的方程：
𝑎′𝑥≡𝑏′(mod𝑛′).a′x≡b′(modn′).
其中，gcd(𝑎′,𝑛′) =1gcd(a′,n′)=1，也就是说，𝑎′a′ 和 𝑛′n′ 互素．这种情形已经在前文解决，所以，可以通过求解逆元得到方程的一个解 𝑥′x′.
显然，𝑥′x′ 也是原方程的一个解．但这并非原方程唯一的解．由于转化后的方程的全体解为
{𝑥′+𝑘𝑛′:𝑘∈𝐙}.{x′+kn′:k∈Z}.
这些解中落在区间 [0,𝑛 −1][0,n−1] 的那些，就是原方程在区间 [0,𝑛 −1][0,n−1] 中的全部解：
𝑥≡(𝑥′+𝑘𝑛′)(mod𝑛),𝑘=0,1,⋯,𝑑−1.x≡(x′+kn′)(modn),k=0,1,⋯,d−1.
总结这两种情形，线性同余方程的 解的数量 等于 𝑑 =gcd(𝑎,𝑛)d=gcd(a,n) 或 00．
用不定方程求解
线性同余方程等价于关于 𝑥,𝑦x,y 的 二元一次不定方程：
𝑎𝑥+𝑛𝑦=𝑏.ax+ny=b.
利用所引页面的讨论，方程有解当且仅当 gcd(𝑎,𝑛) ∣𝑏gcd(a,n)∣b，而且该方程的一组通解是
𝑥=𝑥0+𝑡𝑛𝑑,𝑦=𝑦0−𝑡𝑎𝑑,x=x0+tnd,y=y0−tad,
其中，𝑑 =gcd(𝑎,𝑛)d=gcd(a,n) 是它们的最大公约数，𝑡t 是任意整数．
进而，线性同余方程的通解就是
𝑥≡(𝑥0+𝑡𝑛𝑑)(mod𝑛),𝑡∈𝐙.x≡(x0+tnd)(modn),t∈Z.
将 𝑥0x0 对 𝑛/𝑑n/d 取模就得到同余方程的最小（非负）整数解，也就是上文的 𝑥′x′.
参考实现
本节提供的参考实现可以得到同余方程的最小非负整数解．如果解不存在，则输出 −1−1．
参考实现
C++Python
---|---
---|---
习题
本页面主要译自博文Модульное линейное уравнение первого порядка 与其英文翻译版 Linear Congruence Equation．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．内容有改动．
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, Tiphereth-A, Enter-tainer, MegaOwIer, Xeonacid, Great-designer, Haohu Shen, iamtwz, ksyx, kZime, ouuan, stevebraveman, aofall, c-forrest, CoelacanthusHex, leoleoasd, Marcythm, Menci, Persdre, Phemon, shawlleyw, shuzhouliu, sshwy, StudyingFather, tsentau 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用