跳转至

# 线性同余方程

本文讨论线性同余方程的求解．

## 基本概念

设 𝑎,𝑏,𝑛 a,b,n 为整数，𝑥 x 为未知数，那么，形如

𝑎 𝑥≡𝑏(m o d 𝑛)a x≡b(mod n)

的方程称为 线性同余方程（linear congruence equation）．

求解线性同余方程，需要找到区间 [0,𝑛 −1][0,n−1] 中 𝑥 x 的全部解．当然，将它们加减 𝑛 n 的任意倍数，依然是方程的解．在模 𝑛 n 的意义下，这些就是该方程的全部解．

本文接下来介绍了两种求解线性同余方程的思路，分别利用了逆元和不定方程．对于一般的情形，逆元和不定方程的求解都需要用到 扩展欧几里得算法，因此，这两种思路其实是一致的．

## 用逆元求解

首先，考虑 𝑎 a 和 𝑛 n 互素的情形，即 g c d(𝑎,𝑛) =1 gcd(a,n)=1 的情形．此时，可以计算 𝑎 a 的 逆元 𝑎−1 a−1，并将方程两边同乘以 𝑎−1 a−1，这就得到方程的唯一解：

𝑥≡𝑏 𝑎−1(m o d 𝑛).x≡b a−1(mod n).

紧接着，考虑 𝑎 a 和 𝑛 n 不互素的情形，即 g c d(𝑎,𝑛) =𝑑 >1 gcd(a,n)=d>1 的情形．此时，原方程不一定有解．例如，2 𝑥 ≡1(m o d 4)2 x≡1(mod 4) 就没有解．因此，需要考虑两种情形：

- 当 𝑑 d 不能整除 𝑏 b 时，方程无解．对于任意的 𝑥 x，方程左侧 𝑎 𝑥 a x 都是 𝑑 d 的倍数，但是方程右侧 𝑏 b 不是 𝑑 d 的倍数．因此，它们不可能相差 𝑛 n 的倍数，因为 𝑛 n 的倍数也一定是 𝑑 d 的倍数．因此，方程无解．

- 当 𝑑 d 可以整除 𝑏 b 时，可以将方程的参数 𝑎,𝑏,𝑛 a,b,n 都同除以 𝑑 d，得到一个新的方程：

  𝑎′𝑥≡𝑏′(m o d 𝑛′).a′x≡b′(mod n′).

  其中，g c d(𝑎′,𝑛′) =1 gcd(a′,n′)=1，也就是说，𝑎′a′ 和 𝑛′n′ 互素．这种情形已经在前文解决，所以，可以通过求解逆元得到方程的一个解 𝑥′x′.

  显然，𝑥′x′ 也是原方程的一个解．但这并非原方程唯一的解．由于转化后的方程的全体解为

  {𝑥′+𝑘 𝑛′:𝑘∈𝐙}.{x′+k n′:k∈Z}.

  这些解中落在区间 [0,𝑛 −1][0,n−1] 的那些，就是原方程在区间 [0,𝑛 −1][0,n−1] 中的全部解：

  𝑥≡(𝑥′+𝑘 𝑛′)(m o d 𝑛),𝑘=0,1,⋯,𝑑−1.x≡(x′+k n′)(mod n),k=0,1,⋯,d−1.

总结这两种情形，线性同余方程的 解的数量 等于 𝑑 =g c d(𝑎,𝑛)d=gcd(a,n) 或 0 0．

## 用不定方程求解

线性同余方程等价于关于 𝑥,𝑦 x,y 的 二元一次不定方程：

𝑎 𝑥+𝑛 𝑦=𝑏.a x+n y=b.

利用所引页面的讨论，方程有解当且仅当 g c d(𝑎,𝑛) ∣𝑏 gcd(a,n)∣b，而且该方程的一组通解是

𝑥=𝑥 0+𝑡 𝑛 𝑑,𝑦=𝑦 0−𝑡 𝑎 𝑑,x=x 0+t n d,y=y 0−t a d,

其中，𝑑 =g c d(𝑎,𝑛)d=gcd(a,n) 是它们的最大公约数，𝑡 t 是任意整数．

进而，线性同余方程的通解就是

𝑥≡(𝑥 0+𝑡 𝑛 𝑑)(m o d 𝑛),𝑡∈𝐙.x≡(x 0+t n d)(mod n),t∈Z.

将 𝑥 0 x 0 对 𝑛/𝑑 n/d 取模就得到同余方程的最小（非负）整数解，也就是上文的 𝑥′x′.

## 参考实现

本节提供的参考实现可以得到同余方程的最小非负整数解．如果解不存在，则输出 −1−1．

参考实现
C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    // Extended Euclidean Algorithm.
    // Finds integers x, y such that a*x + b*y = gcd(a, b),
    // and returns gcd(a, b).
    int ex_gcd(int a, int b, int& x, int& y) {
      if (!b) {
        x = 1;
        y = 0;
        return a;
      } else {
        int d = ex_gcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
      }
    }

    // Solves the linear congruence equation:
    //     a * x ≡ b (mod n), where n > 0.
    // Returns the smallest non-negative solution x,
    // or -1 if there is no solution.
    int solve_linear_congruence_equation(int a, int b, int n) {
      int x, y;
      int d = ex_gcd(a, n, x, y);
      if (b % d) return -1;
      n /= d;
      return ((long long)x * (b / d) % n + n) % n;
    }

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    def ex_gcd(a, b):
        """
        Extended Euclidean Algorithm.
        Finds integers x, y such that a*x + b*y = gcd(a, b),
        and returns (gcd, x, y).
        """
        if b == 0:
            return a, 1, 0
        d, x1, y1 = ex_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return d, x, y

    def solve_linear_congruence_equation(a, b, n):
        """
        Solves the linear congruence equation:
            a * x ≡ b (mod n), where n > 0.
        Returns the smallest non-negative solution x,
        or -1 if there is no solution.
        """
        d, x, y = ex_gcd(a, n)
        if b % d != 0:
            return -1
        n //= d
        return (x * (b // d) % n + n) % n

## 习题

- 「NOIP2012」同余方程

本页面主要译自博文 Модульное линейное уравнение первого порядка 与其英文翻译版 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 协议之条款下提供，附加条款亦可能应用