跳转至

线性同余方程

定义

形如

axb(modn)

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

用逆元求解

首先考虑简单的情况,当 an 互素(coprime 或 relatively prime)时,即 gcd(a,n)=1

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

证明

xba1(modn)

接下来考虑 an 不互素(not coprime),即 gcd(a,n)1 的情况。此时不一定有解。例如,2x1(mod4) 没有解。

g=gcd(a,n),即 an 的最大公约数,其中 an 在本例中大于 1。

b 不能被 g 整除时无解。此时,对于任意的 x,方程 axb(modn) 的左侧始终可被 g 整除,而右侧不可被 g 整除,因此无解。

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

axb(modn)

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

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

xi(x+in)(modn)for i=0g1

总之,线性同余方程的 解的数量 等于 g=gcd(a,n) 或等于 0

用扩展欧几里得算法求解

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

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

ax+nk=b

其中 xk 是未知数。这两个方程是等价的,有整数解的充要条件为 gcd(a,n)b

应用扩展欧几里德算法可以求解该线性不定方程。根据定理 1,对于线性不定方程 ax+nk=b,可以先用扩展欧几里得算法求出一组 x0,k0,也就是 ax0+nk0=gcd(a,n),然后两边同时除以 gcd(a,n),再乘 b。就得到了方程

abgcd(a,n)x0+nbgcd(a,n)k0=b

于是找到方程的一个解。

定理 2:若 gcd(a,n)=1,且 x0k0 为方程 ax+nk=b 的一组解,则该方程的任意解可表示为:

x=x0+ntk=k0at

并且对任意整数 t 都成立。

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

x=(xmodt+t)modt

其中有

t=ngcd(a,n)

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

实现

代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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」同余方程