拡張ユークリッドの互除法

2 つの整数 $a$、$b$ に対して、次の式を満たす整数 $x$、$y$ を求めます。

このような $x$、$y$ が必ず存在することを、ベズーの等式といいます。ふつうの互除法は最大公約数だけを求めますが、途中の余りが $a$ と $b$ を何倍ずつ含むかも並べて追っておくと、割り切れた時点で $x$ と $y$ が残ります。

例

$a = 240$、$b = 46$ とします。最大公約数は 2 で、$x = -9$、$y = 47$ が求まります。確かめると $240 \times (-9) + 46 \times 47 = -2160 + 2162 = 2$ になります。

使いどころ

一次不定方程式 $ax + by = c$ が整数の解を持つのは、$c$ が最大公約数の倍数であるときだけです。その解を 1 つ見つけるのに、この計算を使います。

$ax \equiv 1 \pmod{m}$ を満たす $x$、つまり法 $m$ での逆数を求めるのにも使います。$a$ と $m$ が互いに素なら $ax + my = 1$ が解けて、その $x$ が答えです。暗号の計算で使われます。

注意

$x$ と $y$ の組は一通りではありません。$x$ に $\dfrac{b}{\gcd(a, b)}$ を足し、$y$ から $\dfrac{a}{\gcd(a, b)}$ を引いても等式は成り立ちます。ここでは互除法がそのまま返す組を出します。