线性同余方程

定义

形如

的方程称为 线性同余方程(Congruence Equation)。其中, 为给定整数, 为未知数。需要从区间 中求解 ,当解不唯一时需要求出全体解。

用逆元求解

首先考虑简单的情况,当 互素(coprime 或 relatively prime)时,即

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

证明

接下来考虑 不互素(not coprime),即 的情况。此时不一定有解。例如, 没有解。

,即 的最大公约数,其中 在本例中大于 1。

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

如果 整除 ,则通过将方程两边 除以 ,得到一个新的方程:

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

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

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

用扩展欧几里得算法求解

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

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

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

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

于是找到方程的一个解。

定理 2:若 ,且 为方程 的一组解,则该方程的任意解可表示为:

并且对任意整数 都成立。

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

其中有

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

实现

代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// C++ Version
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 0;
  int k = c / d;
  x *= k;
  y *= k;
  return 1;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# Python Version
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」同余方程


评论