109. 一次合同方程式を拡張ユークリッド互除法で解く

一次合同方程式 $ax \equiv b \pmod{m}$ を解くことを考えます。競技プログラミングでは稀に必要となる知識で、たとえば以下のような問題で要求されます。

atcoder.jp

この記事では、

【理論編】一次合同方程式 $ax \equiv b \pmod{m}$ の解の個数
【実装編】拡張ユークリッド互除法による一次合同方程式の解き方

という流れで記述します。

【理論編】一次合同方程式 $ax \equiv b \pmod{m}$ の解の個数

まずは結論から。

一次合同方程式 $ax \equiv b \pmod{m}$ は、 $\gcd(a, m) = d$ として、

$b$ が $d$ の倍数でないなら解を持たない
$b$ が $d$ の倍数であるなら $d$ 個の解を持つ

証明

(1) $\gcd(a, m) = 1$ のとき唯一の解が存在することについて

$\gcd(a, m) = 1$ とする。

$\{x_1, x_2, \dots, x_m\}$ を、 $m$ を法とする剰余系として定める。このとき、 $\{ax_1, ax_2, \dots, ax_m\}$ も $m$ を法とする剰余系となる。
なぜなら、 $ax_i \equiv ax_j \pmod{m}$ となるとき、 $a, m$ は互いに素なので両辺を $a$ で割って $x_i \equiv x_j \pmod{m}$ となり、これは $i = j$ と同値であるため。

よって、任意の $b$ に対して $ax \equiv b \pmod{m}$ となる $x = x_i$ が唯一存在する。

(2) $b$ が $\gcd(a, m)$ の倍数でないとき解が存在しないことについて

$ax \equiv b \pmod{m}$ に解があると仮定すれば、 $ax = b + ms$ （ $s$ は整数）と表せる。変形して $b = ax - ms$ とする。

$\gcd(a, m) = d$ として、 $a = da', m = dm'$ とおくと、 $b = d(a'x - m's)$ と表せる。つまり、 $b$ は $d$ の倍数となる。

よって、 $b$ が $d$ の倍数でないなら、背理法的に解は存在しない。

(3) $b$ が $\gcd(a, m) = d$ の倍数のとき解が $d$ 個存在することについて

(2) の議論の続きで、 $b$ が $d$ の倍数として、 $b = db'$ とおく。あらためて式を整理すると、

$ax \equiv b \pmod{m}$
$\iff ax = b + ms$
$\iff da'x = db' + dm's$
$\iff a'x = b' + m's$
$\iff a'x \equiv b' \pmod{m'}$

ここで、 $a', m'$ はその作成方法から互いに素。よって、 $a'x \equiv b' \pmod{m'}$ の解について、(1) より $x \equiv x' \pmod{m'}$ なる $x'$ （ $0 \le x' \lt m'$ ）が唯一存在し、 $x = x' + m't$ （ $t$ は任意の整数）と表せる。

ここから、元の方程式の解の個数を考える。

$x$ が $m$ を法として合同となるのは、ある $t_1, t_2$ について、 $x \equiv x' \equiv x' + m't_1 \equiv x' + m't_2 \pmod{m}$ となるとき。つまり、 $m'(t_1 - t_2) \equiv 0 \pmod{m}$ となるときで、すなわち、 $m'(t_1 - t_2) = mu$ （ $u$ は整数）であるとき。

このとき、

$m'(t_1 - t_2) = mu$
$\iff \frac{m}{d}(t_1 - t_2) = mu$
$\iff t_1 - t_2 = du$
$\iff t_1 - t_2 \equiv 0 \pmod{d}$

すなわち、 $x$ が $m$ を法として合同となるのは、 $t$ に対して $d$ を法として合同な整数を与えたときであり、よって解は $d$ 個存在する。

（証明終わり）

【実装編】拡張ユークリッド互除法による一次合同方程式の解き方

まず、 $ax \equiv b \pmod{m} \iff ax = b + mt$ （ $t$ は整数）を満たす $x$ を求めたいので、 $\gcd(a, b, m) = d$ として、 $a = da', b = db', m = dm'$ と置いて $a'x = b' + m't \iff a'x \equiv b' \pmod{m'}$ を考えてもよいです。以降、この操作を行った後と考え、 $\gcd(a, b, m) = 1$ であるとします。

$ax \equiv b \pmod{m} \iff x \equiv a^{-1}b \pmod{m}$ を解きたいので、 $a$ の逆元 $a^{-1}$ を考えます。 $m$ は素数であるとは限らないので、フェルマーの小定理による逆元導出は使えません。

ここで、逆元を導出するための一次合同方程式は $ax \equiv 1 \pmod{m}$ と表せます。先程の証明 (2)(3) より、逆元が存在するためには $\gcd(a, m) = 1$ であることが必要です。よって、 $\gcd(a, m) \neq 1$ のとき、解は存在しません。