线性同余方程

定义

形如

的方程称为 线性同余方程（Linear Congruence Equation）。其中，、和为给定整数，为未知数。需要从区间中求解，当解不唯一时需要求出全体解。

用逆元求解

首先考虑简单的情况，当和互素（coprime 或 relatively prime）时，即。

此时可以计算的逆元，并将方程的两边乘以的逆元，可以得到唯一解。

证明

接下来考虑和不互素（not coprime），即的情况。此时不一定有解。例如，没有解。

设，即和的最大公约数，其中和在本例中大于 1。

当不能被整除时无解。此时，对于任意的，方程的左侧始终可被整除，而右侧不可被整除，因此无解。

如果整除，则通过将方程两边、和除以，得到一个新的方程：

其中和已经互素，这种情形已经解决，于是得到作为的解。

很明显，也将是原始方程的解。这不是唯一的解。可以看出，原始方程有如下个解：

总之，线性同余方程的 解的数量 等于或等于。

用扩展欧几里得算法求解

根据以下两个定理，可以求出线性同余方程的解。

定理 1：线性同余方程可以改写为如下线性不定方程：

其中和是未知数。这两个方程是等价的，有整数解的充要条件为。

应用扩展欧几里德算法可以求解该线性不定方程。根据定理 1，对于线性不定方程，可以先用扩展欧几里得算法求出一组，也就是，然后两边同时除以，再乘。就得到了方程

于是找到方程的一个解。

定理 2：若，且、为方程的一组解，则该方程的任意解可表示为：

并且对任意整数都成立。

根据定理 2，可以从已求出的一个解，求出方程的所有解。实际问题中，往往要求出一个最小整数解，也就是一个特解

其中有

如果仔细考虑，用扩展欧几里得算法求解与用逆元求解，两种方法是等价的。

实现

代码实现

C++Python

int ex_gcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int d = ex_gcd(b, a % b, x, y);
  int temp = x;
  x = y;
  y = temp - a / b * y;
  return d;
}

bool liEu(int a, int b, int c, int& x, int& y) {
  int d = ex_gcd(a, b, x, y);
  if (c % d != 0) return false;
  int k = c / d;
  x *= k;
  y *= k;
  return true;
}

def ex_gcd(a, b, x, y):
    if b == 0:
        x = 1
        y = 0
        return a
    d = ex_gcd(b, a % b, x, y)
    temp = x
    x = y
    y = temp - a // b * y
    return d


def liEu(a, b, c, x, y):
    d = ex_gcd(a, b, x, y)
    if c % d != 0:
        return 0
    k = c // d
    x = x * k
    y = y * k
    return 1

本页面主要译自博文 Модульное линейное уравнение первого порядка 与其英文翻译版 Linear Congruence Equation。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。

习题

「NOIP2012」同余方程

最后更新: 2024年10月9日
创建日期: 2018年7月11日