第3章 ユークリッドの互除法

最大公約数を効率的に求めるアルゴリズム

導入

ユークリッドの互除法（Euclidean algorithm）は、2つの正整数の最大公約数（GCD）を効率的に求めるアルゴリズムである。紀元前300年頃のユークリッドの『原論』に記載されており、人類最古のアルゴリズムの一つとされる。

なぜ互除法が必要か？

素因数分解を経由してGCDを求める方法は、数が大きくなると試し割りの回数が増え、効率が悪い。互除法を使えば、$\gcd(12345678, 87654321)$ もわずか13回の除算で求められる。

互除法の原理

定理（互除法の原理）

正整数 $a, b$（$a > b$）に対して、$a$ を $b$ で割った商を $q$、余りを $r$ とすると

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

このとき

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

証明

$d = \gcd(a, b)$ とおく。$d \mid a$ かつ $d \mid b$ である。

Step 1：$d \mid r$ を示す

$r = a - bq$ より、$d \mid a$ かつ $d \mid bq$ なので $d \mid r$

Step 2：$\gcd(b, r) = d$ を示す

$d$ は $b$ と $r$ の公約数である。

$d' = \gcd(b, r)$ とすると、$d' \mid b$ かつ $d' \mid r$ より

$d' \mid (bq + r) = a$

よって $d'$ は $a$ と $b$ の公約数なので $d' \leq d$

一方 $d \leq d'$（$d$ は $b, r$ の公約数）なので $d = d'$

したがって $\gcd(a, b) = \gcd(b, r)$ $\square$

a b b b r q 個の b a と b の公約数 ⇔ b と r の公約数 （余り r が小さいので問題が簡単になる！）
図1：互除法の原理 $\gcd(a, b) = \gcd(b, r)$

アルゴリズム

ユークリッドの互除法

入力：正整数 $a, b$（$a \geq b$）

出力：$\gcd(a, b)$

  1. $r \leftarrow a \mod b$（$a$ を $b$ で割った余り）
  2. $r = 0$ ならば $b$ を出力して終了
  3. $a \leftarrow b$, $b \leftarrow r$ として 1 へ戻る

例：$\gcd(252, 105)$ を求める

\begin{align} 252 &= 105 \times 2 + 42 & \gcd(252, 105) &= \gcd(105, 42) \\ 105 &= 42 \times 2 + 21 & \gcd(105, 42) &= \gcd(42, 21) \\ 42 &= 21 \times 2 + 0 & \gcd(42, 21) &= 21 \end{align}

答：$\gcd(252, 105) = 21$

252 ÷ 105 = 2 余り 42 105 ÷ 42 = 2 余り 21 42 ÷ 21 = 2 余り 0 終了！
$\gcd(252, 105) = 21$
図2：gcd(252, 105) の計算過程

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

定理（ベズーの等式）

整数 $a, b$ に対して、$d = \gcd(a, b)$ とすると、

$$ax + by = d$$

を満たす整数 $x, y$ が存在する。

証明（構成的）

ユークリッドの互除法の各ステップを逆にたどることで $x, y$ を求められる。

例：$\gcd(252, 105) = 21$ に対して $252x + 105y = 21$ を満たす $x, y$ を求める

互除法の過程を式で表す：

\begin{align} 252 &= 105 \times 2 + 42 & \Rightarrow \quad 42 &= 252 - 105 \times 2 \\ 105 &= 42 \times 2 + 21 & \Rightarrow \quad 21 &= 105 - 42 \times 2 \end{align}

逆代入：

\begin{align} 21 &= 105 - 42 \times 2 \\ &= 105 - (252 - 105 \times 2) \times 2 \\ &= 105 - 252 \times 2 + 105 \times 4 \\ &= 252 \times (-2) + 105 \times 5 \end{align}

したがって $x = -2, y = 5$ $\square$

代入 x = −2 y = 5
$42 = 252 - 105 \times 2$
$21 = 105 - 42 \times 2$
$21 = 105 - (252 - 105 \times 2) \times 2$
$21 = 252 \times (-2) + 105 \times 5$
図3：拡張ユークリッド互除法（逆代入）

1次不定方程式への応用

定理：1次不定方程式の解

整数 $a, b, c$ に対して、$ax + by = c$ が整数解を持つ条件は

$$\gcd(a, b) \mid c$$

（$\gcd(a, b)$ が $c$ を割り切る）

証明

必要性：$d = \gcd(a, b)$ とすると、$d \mid a$ かつ $d \mid b$ なので $d \mid (ax + by) = c$

十分性：$d \mid c$ のとき、$c = dk$ とおける。

ベズーの等式より $ax_0 + by_0 = d$ となる $x_0, y_0$ が存在する。

両辺を $k$ 倍すると $a(kx_0) + b(ky_0) = dk = c$

よって $x = kx_0, y = ky_0$ が解。$\square$

一般解

$ax + by = c$ の特殊解を $(x_0, y_0)$、$d = \gcd(a, b)$ とすると、一般解は

$$x = x_0 + \frac{b}{d}t, \quad y = y_0 - \frac{a}{d}t \quad (t \in \mathbb{Z})$$

例題

$252x + 105y = 63$ の整数解をすべて求めよ。

解答

$\gcd(252, 105) = 21$ で $21 \mid 63$（$63 = 21 \times 3$）なので解が存在する。

$252 \times (-2) + 105 \times 5 = 21$ を3倍すると

$252 \times (-6) + 105 \times 15 = 63$

特殊解：$(x_0, y_0) = (-6, 15)$

一般解：$x = -6 + 5t, \quad y = 15 - 12t \quad (t \in \mathbb{Z})$

互除法の効率性

定理（ラメの定理）

ユークリッドの互除法で $\gcd(a, b)$ を計算するとき（$a > b$）、除算の回数は $b$ の10進表記の桁数の5倍以下である。

計算量

ユークリッドの互除法の計算量は $O(\log(\min(a, b)))$ である。これは非常に効率的であり、RSA暗号などの実用的なアルゴリズムの基盤となっている。

最悪ケースは隣接するフィボナッチ数の組 $\gcd(F_{n+1}, F_n)$ であり、各ステップで商が常に $1$ となるため余りの減少が最も遅い。証明は初級：ユークリッドの互除法で扱う。

大きな数の例

$\gcd(12345678, 87654321)$ を求める：

\begin{align} 87654321 &= 12345678 \times 7 + 1034475 \\ 12345678 &= 1034475 \times 11 + 966453 \\ 1034475 &= 966453 \times 1 + 68022 \\ 966453 &= 68022 \times 14 + 14145 \\ 68022 &= 14145 \times 4 + 11442 \\ 14145 &= 11442 \times 1 + 2703 \\ 11442 &= 2703 \times 4 + 630 \\ 2703 &= 630 \times 4 + 183 \\ 630 &= 183 \times 3 + 81 \\ 183 &= 81 \times 2 + 21 \\ 81 &= 21 \times 3 + 18 \\ 21 &= 18 \times 1 + 3 \\ 18 &= 3 \times 6 + 0 \end{align}

答：$\gcd(12345678, 87654321) = 3$

（わずか13回の除算で完了。素因数分解で求める方法に比べて圧倒的に高速）