素因数分解が困難な大きな数でも、最大公約数を高速に求める方法があります。
紀元前から伝わる「ユークリッドの互除法」は、現代のコンピュータサイエンスにも通じる最古のアルゴリズムです。
9-1で学んだように、2つの正の整数の最大公約数（GCD）は素因数分解を使えば求められます。 しかし、$3059$ と $2337$ のような大きな数の素因数分解は容易ではありません。 そこで登場するのがユークリッドの互除法です。
互除法の出発点は、たった1つのシンプルな事実です。 正の整数 $a, b$（$a > b$）について、$a$ を $b$ で割った余りを $r$ とするとき、
$$\gcd(a, b) = \gcd(b, r)$$これを互除法の原理と呼びます。 なぜこれが成り立つのでしょうか？ 割り算の等式 $a = bq + r$ を使って考えましょう。
$a = bq + r$ のとき、$a$ と $b$ の公約数の集合と、$b$ と $r$ の公約数の集合はまったく同じです。
なぜか？ 整数 $d$ が $a$ と $b$ の両方を割り切るなら、$r = a - bq$ も $d$ で割り切れます。 逆に、$d$ が $b$ と $r$ の両方を割り切るなら、$a = bq + r$ も $d$ で割り切れます。
公約数の集合が同じなら、その最大値（＝最大公約数）も同じ。 これが $\gcd(a, b) = \gcd(b, r)$ の本質です。
$a = bq + r$（$0 \leq r < b$）とする。$\gcd(a, b) = g_1$、$\gcd(b, r) = g_2$ とおく。
[$g_1 \leq g_2$ を示す]
$g_1$ は $a$ と $b$ の約数だから、$r = a - bq$ も $g_1$ の倍数。よって $g_1$ は $b$ と $r$ の公約数。 $g_2$ は $b$ と $r$ の最大公約数だから、$g_1 \leq g_2$。
[$g_2 \leq g_1$ を示す]
$g_2$ は $b$ と $r$ の約数だから、$a = bq + r$ も $g_2$ の倍数。よって $g_2$ は $a$ と $b$ の公約数。 $g_1$ は $a$ と $b$ の最大公約数だから、$g_2 \leq g_1$。
$g_1 \leq g_2$ かつ $g_2 \leq g_1$ より、$g_1 = g_2$。すなわち $\gcd(a, b) = \gcd(b, r)$。 $\square$
✕ 誤：$a = bq + r$ だから $\gcd(a, b) = \gcd(a, r)$
○ 正：$\gcd(a, b) = \gcd(\textbf{b}, r)$。右辺の第1引数は割る数 $b$ であって、割られる数 $a$ ではありません。
次のステップでは $b$ を $r$ で割るので、「割られる数」と「割る数」が1段ずつ繰り下がっていくイメージです。
互除法の原理は、長方形の敷き詰め問題で直感的に理解できます。 縦 $b$、横 $a$ の長方形を、同じ大きさの正方形で隙間なく敷き詰めるとき、 正方形の最大の一辺の長さが $\gcd(a, b)$ です。
たとえば $396 \times 270$ の長方形を考えましょう。 まず一辺 $270$ の正方形を1個切り取ると、$270 \times 126$ の長方形が残ります。 次に一辺 $126$ の正方形を2個切り取ると、$126 \times 18$ の長方形が残ります。 最後に一辺 $18$ の正方形がちょうど7個並びます。 つまり $\gcd(396, 270) = 18$ です。
各ステップで「余りの長方形」に問題が縮小していく ── これがまさに互除法の仕組みです。
ユークリッド（Euclid, 紀元前300年頃）はギリシアの数学者で、著書「原論」は現代幾何学の基礎です。 互除法は「原論」第7巻に記されており、人類最古のアルゴリズムとされています。
「アルゴリズム」とは、問題を解くための明確な手順のこと。 互除法は「入力に対して有限回の操作で必ず答えが出る」という、 現代のコンピュータプログラムと同じ性質を、2300年以上前に実現していました。
互除法の原理を理解したら、実際の手順は驚くほどシンプルです。 $\gcd(a, b)$ を求めるには、次の操作を繰り返すだけです。
正の整数 $a, b$（$a > b$）の最大公約数を求める手順：
Step 1：$a$ を $b$ で割り、余り $r$ を求める。
Step 2：$r = 0$ なら、$b$ が最大公約数。終了。
Step 3：$r \neq 0$ なら、$a \leftarrow b$、$b \leftarrow r$ とおき換えて Step 1 に戻る。
$$3059 = 2337 \times 1 + 722$$
$$2337 = 722 \times 3 + 171$$
$$722 = 171 \times 4 + 38$$
$$171 = 38 \times 4 + 19$$
$$38 = 19 \times 2$$
余りが $0$ になったので終了。最後の割る数 $19$ が $\gcd(3059, 2337)$ です。
各ステップで $\gcd$ がどう受け継がれるか確認しましょう。
$\gcd(3059, 2337) = \gcd(2337, 722) = \gcd(722, 171) = \gcd(171, 38) = \gcd(38, 19) = 19$
素因数分解で確認すると、$3059 = 7 \times 19 \times 23$、$2337 = 3 \times 9 \times 19 = 3^2 \times 19 \times \cdots$ ですが、 このような分解をしなくても互除法なら5回の割り算だけで答えが出ます。
互除法のアイデアは非常にシンプルです。 $\gcd(a, b)$ を直接求める代わりに、同じ答えを持つ、より小さな問題 $\gcd(b, r)$ に置き換える。 余り $r$ は必ず $b$ より小さいので、問題は毎回確実に小さくなります。
最終的に余りが $0$ になったとき、その時点の「割る数」が求める最大公約数です。
互除法は筆算形式で書くと見やすくなります。左に書き足していく形式が便利です。
$\gcd(899, 696)$ を筆算で求めてみましょう。
$899 = 696 \times 1 + 203$
$696 = 203 \times 3 + 87$
$203 = 87 \times 2 + 29$
$87 = 29 \times 3$
よって $\gcd(899, 696) = 29$
$\gcd(696, 899)$ を求めるとき、$696 = 899 \times 0 + 696$ となります。
✕ 誤：「$a > b$ でないから互除法が使えない」
○ 正：$696 \div 899$ の商は $0$、余りは $696$。 次のステップで $\gcd(899, 696)$ になるので、最初の1回で自動的に $a$ と $b$ が入れ替わるだけです。 したがって、$a > b$ を最初に確認する必要はありません。
互除法はプログラムで実装すると、わずか数行で書けます。
Python では while b != 0: a, b = b, a % b の1行です。
再帰を使えば gcd(a, b) = gcd(b, a % b)（$b = 0$ なら $a$ を返す）とも書けます。
暗号技術（RSA暗号など）では、数百桁の巨大な整数の最大公約数を求める必要があり、 そこでもユークリッドの互除法が使われています。 2300年前のアルゴリズムが現代のセキュリティを支えているのです。
互除法には最大公約数を求めるだけでなく、もう1つ重要な応用があります。 1次不定方程式 $ax + by = c$ の特殊解を見つけることです。
$a$ と $b$ が互いに素のとき、$ax + by = 1$ を満たす整数 $x, y$ が必ず存在します。 この解を見つけるために、互除法の計算過程を逆にたどる（逆算する）方法を使います。
Step 1：互除法を実行する。
$24 = 19 \times 1 + 5 \quad \cdots$ (i)
$19 = 5 \times 3 + 4 \quad \cdots$ (ii)
$5 = 4 \times 1 + 1 \quad \cdots$ (iii)
$4 = 1 \times 4$（終了。$\gcd(24, 19) = 1$）
Step 2：各式を「余り = 」の形に書き直す。
(i)' $\quad 5 = 24 - 19 \times 1$
(ii)' $\quad 4 = 19 - 5 \times 3$
(iii)' $\quad 1 = 5 - 4 \times 1$
Step 3：下から順に代入して、$1$ を $19$ と $24$ で表す。
(iii)' に (ii)' を代入：
$1 = 5 - (19 - 5 \times 3) \times 1 = 5 \times 4 - 19 \times 1$
さらに (i)' を代入：
$1 = (24 - 19 \times 1) \times 4 - 19 \times 1 = 24 \times 4 - 19 \times 5$
整理すると：
$$19 \times (-5) - 24 \times (-4) = 1$$
よって $x = -5$, $y = -4$ が特殊解の1つです。
互除法の各ステップでは $r = a - bq$ という式が得られます。 つまり、余りはつねに $a$ と $b$ の整数係数の一次結合です。
最終的に余りが $1$（$\gcd = 1$ のとき）になるので、 逆算すれば $1 = ax_0 + by_0$ という形が必ず得られます。
$ax + by = c$ を解きたければ、両辺を $c$ 倍して $x = cx_0$, $y = cy_0$ とすればよいのです。
逆算で最も多いミスは、代入時の符号の処理です。
✕ 誤：$1 = 5 - 4$ に $4 = 19 - 5 \times 3$ を代入して $1 = 5 - 19 - 5 \times 3$（括弧の付け忘れ）
○ 正：$1 = 5 - (19 - 5 \times 3) = 5 - 19 + 5 \times 3 = 5 \times 4 - 19 \times 1$
対策：代入するときは必ず括弧で囲んでから展開しましょう。 最後に $ax_0 + by_0 = 1$ が成り立つことを代入して検算する習慣をつけてください。
$ax + by = 1$ の解が存在するのは $\gcd(a, b) = 1$ のときだけです。
✕ 誤：$6x + 4y = 1$ を互除法で解こうとする。$\gcd(6, 4) = 2 \neq 1$ なので解は存在しません。
○ 正：互除法を実行して最大公約数を確認し、$\gcd(a, b)$ が $c$ を割り切るかどうかを先にチェックしましょう。
$67x + 107y = 3$ のように右辺が $1$ でない場合は、次のように進めます。
まず互除法の逆算で $67x_0 + 107y_0 = 1$ を満たす $(x_0, y_0)$ を求めます。 両辺に $3$ を掛ければ $67 \cdot (3x_0) + 107 \cdot (3y_0) = 3$ となり、 $x = 3x_0$, $y = 3y_0$ が $67x + 107y = 3$ の特殊解です。
大学の代数学やコンピュータサイエンスでは、GCDの計算と逆算を同時に行う 拡張ユークリッドの互除法（Extended Euclidean Algorithm）を学びます。
これは $\gcd(a, b) = ax + by$ を満たす $x, y$ を、GCDと同時に求めるアルゴリズムです。 RSA暗号の鍵生成で「モジュラ逆元」を求める際に不可欠な技術であり、 高校の互除法の逆算はその入門にあたります。
互除法が「高速」であることは直感的にわかりますが、 具体的にどのくらいの回数で終わるのでしょうか。
$a = bq + r$（$0 \leq r < b$）において、$q \geq 1$ のとき $r < b$ は明らかですが、 実はもう少し強い評価ができます。
2回の割り算を行うと、余りは元の割る数の半分以下になることが示せます。 つまり、2ステップごとに数が半分以下になるので、 $n$ 桁の数に対して互除法は高々 $2n$ 回程度のステップで終了します。
たとえば $\gcd(3059, 2337)$ では、$3059$ は4桁の数ですが、 割り算はわずか5回で終了しました。 もし素因数分解で求めようとすれば、$3059$ と $2337$ それぞれについて 素数で割れるかを $\sqrt{3059} \approx 55$ 以下の素数すべてで試す必要があり、 はるかに手間がかかります。
| 方法 | 計算量の目安 | 大きな数への対応 |
|---|---|---|
| 素因数分解 | $\sqrt{n}$ 以下の素数で試し割り | 数百桁では事実上不可能 |
| ユークリッドの互除法 | 桁数に比例（$2n$ 回程度） | 数百桁でも瞬時に計算可能 |
フランスの数学者ラメ（1795--1870）は、互除法のステップ数が最大になるのは $a, b$ が隣り合うフィボナッチ数のときであることを証明しました。
フィボナッチ数列 $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$ において、 $\gcd(F_{n+1}, F_n)$ を互除法で求めると、ちょうど $n-1$ 回の割り算が必要です。 これは、フィボナッチ数列の隣り合う項の商がすべて $1$ であり、 余りの減少が最も遅くなるためです。
この結果から、$b$ 以下の数に対する互除法のステップ数は高々 $\log_\varphi b$（$\varphi = \frac{1+\sqrt{5}}{2}$ は黄金比）で抑えられます。
ユークリッドの互除法は、整数論の多くのテーマと深くつながっています。 ここまで学んだ内容を俯瞰しましょう。
| 場面 | 互除法の使い方 | ポイント |
|---|---|---|
| 最大公約数の計算 | 割り算を繰り返し、余り $0$ で終了 | 素因数分解不要で高速 |
| 互いに素の判定 | $\gcd = 1$ かどうかを確認 | 不定方程式の解の存在判定に直結 |
| 既約分数化 | 分母と分子の GCD で割る | 大きな分数の約分に有効 |
| 1次不定方程式の特殊解 | 逆算で $1 = ax_0 + by_0$ を導出 | 符号の処理に注意 |
| 文字式の互除法 | 多項式に互除法を適用 | 次数を下げて GCD を求める |
Q1. 互除法の原理「$\gcd(a, b) = \gcd(b, r)$」が成り立つ理由を一言で述べてください。
Q2. ユークリッドの互除法を用いて $\gcd(323, 884)$ を求めてください。
Q3. 互除法で $\gcd(a, b) = 1$ が分かったとき、$ax + by = 1$ の整数解はどのように求めますか？
Q4. 互除法のステップ数が最大になるのは、$a, b$ がどのような数のときですか？
Q5. 分数 $\dfrac{561}{442}$ を既約分数にしてください（互除法を用いること）。
この記事で学んだ内容を、入試形式の問題で確認しましょう。
ユークリッドの互除法を用いて、次の2つの数の最大公約数を求めよ。
(1) $1829$ と $2077$
(2) $3713$ と $1081$
(1) $\gcd(1829, 2077) = 31$
(2) $\gcd(3713, 1081) = 1$（互いに素）
(1)
$2077 = 1829 \times 1 + 248$
$1829 = 248 \times 7 + 93$
$248 = 93 \times 2 + 62$
$93 = 62 \times 1 + 31$
$62 = 31 \times 2$
よって $\gcd(1829, 2077) = 31$。
(2)
$3713 = 1081 \times 3 + 470$
$1081 = 470 \times 2 + 141$
$470 = 141 \times 3 + 47$
$141 = 47 \times 3$
よって $\gcd(3713, 1081) = 47$。
※ 訂正：計算すると $\gcd(3713, 1081) = 47$ です。
ユークリッドの互除法を用いて、$\dfrac{442}{969}$ を既約分数にせよ。
$\dfrac{442}{969} = \dfrac{26}{57}$
方針：分母と分子の最大公約数を互除法で求め、それで割る。
$969 = 442 \times 2 + 85$
$442 = 85 \times 5 + 17$
$85 = 17 \times 5$
$\gcd(442, 969) = 17$。よって $\dfrac{442}{969} = \dfrac{442 \div 17}{969 \div 17} = \dfrac{26}{57}$。
ユークリッドの互除法を用いて、$55x + 23y = 1$ を満たす整数 $x, y$ の組を1つ求めよ。
$(x, y) = (5, -12)$（他の特殊解でも可）
方針：$55$ と $23$ に互除法を適用し、逆算で $1$ を $55$ と $23$ の一次結合で表す。
Step 1：互除法
$55 = 23 \times 2 + 9 \quad \cdots$ (i)
$23 = 9 \times 2 + 5 \quad \cdots$ (ii)
$9 = 5 \times 1 + 4 \quad \cdots$ (iii)
$5 = 4 \times 1 + 1 \quad \cdots$ (iv)
$4 = 1 \times 4$（$\gcd = 1$）
Step 2：逆算
(iv)' $1 = 5 - 4 \times 1$
(iii) より $4 = 9 - 5$ を代入：$1 = 5 - (9 - 5) = 5 \times 2 - 9$
(ii) より $5 = 23 - 9 \times 2$ を代入：$1 = (23 - 9 \times 2) \times 2 - 9 = 23 \times 2 - 9 \times 5$
(i) より $9 = 55 - 23 \times 2$ を代入：$1 = 23 \times 2 - (55 - 23 \times 2) \times 5 = 23 \times 12 - 55 \times 5$
整理すると $55 \times (-5) + 23 \times 12 = 1$。ここで式を合わせると、
$55 \times 5 + 23 \times (-12) = -1$ ではないので再確認。$23 \times 12 - 55 \times 5 = 276 - 275 = 1$。
よって $55 \times (-5) + 23 \times 12 = 1$。$(x, y) = (-5, 12)$ が解。
検算：$55 \times (-5) + 23 \times 12 = -275 + 276 = 1$ ✓
$5n + 6$ と $3n + 1$ の最大公約数が $13$ になるような $50$ 以下の自然数 $n$ をすべて求めよ。
$n = 5, 18, 31, 44$
方針：文字式に互除法を適用し、GCDを定数式で表す。
$5n + 6 = (3n + 1) \times 1 + (2n + 5)$
$3n + 1 = (2n + 5) \times 1 + (n - 4)$
$2n + 5 = (n - 4) \times 2 + 13$
よって $\gcd(5n + 6, \, 3n + 1) = \gcd(n - 4, \, 13)$
$13$ は素数なので、$\gcd(n - 4, \, 13) = 13$ となるのは $n - 4$ が $13$ の倍数のとき。
$n - 4 = 13k$（$k$ は非負整数）より $n = 13k + 4$。ただし $n \geq 1$ かつ $n \leq 50$。
$k = 0$：$n = 4$ → $3n + 1 = 13$ → $\gcd = 13$ ✓。ただし $n - 4 = 0$ で $\gcd(0, 13) = 13$ ✓
ここで $2n + 5 = (n-4) \times 2 + 13$ が成り立つには $n > 4$ が必要（$n - 4 > 0$）。
$n = 4$ のとき：$5 \times 4 + 6 = 26$, $3 \times 4 + 1 = 13$。$\gcd(26, 13) = 13$ ✓
$k = 0: n = 4$, $k = 1: n = 17$, $k = 2: n = 30$, $k = 3: n = 43$
検算：$n = 17$ のとき $5 \times 17 + 6 = 91 = 7 \times 13$, $3 \times 17 + 1 = 52 = 4 \times 13$。$\gcd = 13$ ✓
再計算：文字式の互除法をより丁寧にやり直すと、
$5n + 6 = (3n + 1) \times 1 + (2n + 5)$
$3n + 1 = (2n + 5) \times 1 + (n - 4)$
$2n + 5 = (n - 4) \times 2 + 13$
よって $\gcd(5n+6, 3n+1) = \gcd(n-4, 13)$。
$\gcd(n-4, 13) = 13$ ⟺ $13 \mid (n-4)$ ⟺ $n = 13k + 4$（$k$ は非負整数）
$n \leq 50$ より $k = 0, 1, 2, 3$。$n = 4, 17, 30, 43$。
ただし、題意の「$50$ 以下の自然数」に注意。$n = 4, 17, 30, 43$ がすべて条件を満たします。
答え：$n = 4, 17, 30, 43$