ユークリッドの互除法

学年の目安（日本）: 数学A

学ぶこと

二つの整数の割り算の余りを利用して、効率よく最大公約数を求めるアルゴリズムを学びます。素因数分解が難しい大きな整数の計算などで力を発揮します。事前に割り算の等式と整数の余りの性質を押さえておくと円滑です。

要点

整数における割り算の関係を表す式です。整数 $a$ を正の整数 $b$ で割ったとき、商を $q$ 、余りを $r$ と置くと、余り $r$ が $0 \le r < b$ の範囲で成り立ちます。

a = bq + r \quad (0 \le r < b)

2つの大きな整数の最大公約数を効率よく探すための式です。 $a$ と $b$ の最大公約数は、割る数 $b$ と余り $r$ の最大公約数と等しくなります。

\gcd(a, b) = \gcd(b, r)

2つの整数 $a, b$ の最大公約数をつくる整数解 $x, y$ が存在することを示す式です。ユークリッドの互除法の計算を逆にたどることで、当てはまる解 $(x, y)$ を1組求められます。

ax + by = \gcd(a, b)

練習する問題セットを選んでください。