跳转至

線性同餘方程

定義

形如

\[ ax\equiv b\pmod n \]

的方程稱為 線性同餘方程（Linear Congruence Equation）。其中，\(a\)、\(b\) 和 \(n\) 為給定整數，\(x\) 為未知數。需要從區間 \([0, n-1]\) 中求解 \(x\)，當解不唯一時需要求出全體解。

用逆元求解

首先考慮簡單的情況，當 \(a\) 和 \(n\) 互素（coprime 或 relatively prime）時，即 \(\gcd(a, n) = 1\)。

此時可以計算 \(a\) 的逆元，並將方程的兩邊乘以 \(a\) 的逆元，可以得到唯一解。

證明

\[ x\equiv ba ^ {- 1} \pmod n \]

接下來考慮 \(a\) 和 \(n\) 不互素（not coprime），即 \(\gcd(a, n) \ne 1\) 的情況。此時不一定有解。例如，\(2x\equiv 1\pmod 4\) 沒有解。

設 \(g = \gcd(a, n)\)，即 \(a\) 和 \(n\) 的最大公約數，其中 \(a\) 和 \(n\) 在本例中大於 1。

當 \(b\) 不能被 \(g\) 整除時無解。此時，對於任意的 \(x\)，方程 \(ax\equiv b\pmod n\) 的左側始終可被 \(g\) 整除，而右側不可被 \(g\) 整除，因此無解。

如果 \(g\) 整除 \(b\)，則通過將方程兩邊 \(a\)、\(b\) 和 \(n\) 除以 \(g\)，得到一個新的方程：

\[ a^{'}x\equiv b^{'} \pmod{n^{'}} \]

其中 \(a^{'}\) 和 \(n^{'}\) 已經互素，這種情形已經解決，於是得到 \(x^{'}\) 作為 \(x\) 的解。

很明顯，\(x^{'}\) 也將是原始方程的解。這不是唯一的解。可以看出，原始方程有如下 \(g\) 個解：

\[ x_i\equiv (x^{'} + i\cdot n^{'}) \pmod n \quad \text{for } i = 0 \ldots g-1 \]

總之，線性同餘方程的 解的數量 等於 \(g = \gcd(a, n)\) 或等於 \(0\)。

用擴展歐幾里得算法求解

根據以下兩個定理，可以求出線性同餘方程 \(ax\equiv b \pmod n\) 的解。

定理 1：線性同餘方程 \(ax\equiv b \pmod n\) 可以改寫為如下線性不定方程：

\[ ax + nk = b \]

其中 \(x\) 和 \(k\) 是未知數。這兩個方程是等價的，有整數解的充要條件為 \(\gcd(a,n) \mid b\)。

應用擴展歐幾里德算法可以求解該線性不定方程。根據定理 1，對於線性不定方程 \(ax+nk=b\)，可以先用擴展歐幾里得算法求出一組 \(x_0,k_0\)，也就是 \(ax_0+nk_0=\gcd(a,n)\)，然後兩邊同時除以 \(\gcd(a,n)\)，再乘 \(b\)。就得到了方程

\[ a\dfrac{b}{\gcd(a,n)}x_0+n\dfrac{b}{\gcd(a,n)}k_0=b \]

於是找到方程的一個解。

定理 2：若 \(\gcd(a,n)=1\)，且 \(x_0\)、\(k_0\) 為方程 \(ax+nk=b\) 的一組解，則該方程的任意解可表示為：

\[ x=x_0+nt \]
\[ k=k_0-at \]

並且對任意整數 \(t\) 都成立。

根據定理 2，可以從已求出的一個解，求出方程的所有解。實際問題中，往往要求出一個最小整數解，也就是一個特解

\[ x=(x \bmod t+t) \bmod t \]

其中有

\[ t=\dfrac{n}{\gcd(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 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
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」同餘方程

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用