1.5.1. 一次不定方程式の整数解¶
ベズーの等式¶
概要¶
Bézout’s identity (Wikipedia)
\(a, b\) を整数とし、\(ax + by = \gcd(a, b)\) という一次不定方程式を考える。このとき次が成り立つ。
\(\gcd(a, b)\) は \(ax + by\) の形で表現できる最小の正の整数である。
どのような整数解 \((x, y)\) に対しても、 \(ax + by\) は \(\gcd(a, b)\) の倍数になる。
整数解がある場合¶
\(8x + 6y = 10\) は整数解をもつ。
整数解がある場合、整数解の候補は無限に存在する。
拡張ユークリッドの互除法¶
Extended Euclidean algorithm (Wikipedia)
と式変形できる。よって \(ax + by = \gcd(a, b)\) の整数解 \((x, y)\) を求めるには
\(b(px + y) + qx = \gcd(a, b)\) の整数解 \((x', y') = (px + y, q)\) を求める
\((x, y) = (y', x' - py')\) を計算する
と手順を定め、手順1を再帰的に実行すればよい。
実装¶
概要¶
一次不定方程式 \(ax + by = c\) の整数解の1つを求める。
例えば \(8x + 6y = 10\) の整数解の1つを求めるには以下の手順を踏む。
拡張ユークリッドの互除法で \(8x + 6y = 2\) の整数解の1つを求める。 \((x, y) = (1, -1)\) が求まる。
ベズーの等式で解の存在判定を行う。 \(\gcd(8, 6) = 2\) であり、右辺 \(10\) は \(2\) の倍数なので、整数解が存在する。
手順1で得られた整数解を \(10 / 2 = 5\) 倍すると、\(8x + 6y = 10\) の整数解の1つが得られる。 \((x, y) = (5, -5)\) が求まる。
手順3で整数解を \(c/gcd(a, b)\) 倍しているが、これは直線 \(ax + by = \gcd(a,b)\) を拡大変換することに相当する。
実装のポイント¶
拡張ユークリッドの互除法では整数解だけでなく最大公約数も求まるので、手順2における解の存在判定にはそれを使えばよい。
計算量¶
extgcd(a, b)\(\mathcal{O}(\log{\min(a, b)})\)solve_linear_equation(a, b, c)\(\mathcal{O}(\log{\min(a, b)})\)
コード¶
[1]:
from __future__ import annotations
def extgcd(a: int, b: int) -> tuple[int, int, int]:
if b == 0:
return (a, 1, 0) if a > 0 else (0, 0, 0)
p, q = divmod(a, b)
d, x, y = extgcd(b, q)
return (d, y, x - p * y)
def solve_linear_equation(a: int, b: int, c: int) -> tuple[bool, int, int]:
d, x, y = extgcd(a, b)
p, q = divmod(c, d)
if q > 0:
return (False, 0, 0)
else:
return (True, x * p, y * p)