ユークリッドの互除法

ユークリッドの互除法とは

ユークリッドの互除法は、二つの自然数の最大公約数を求めるためのアルゴリズムの一つです。紀元前300年頃にユークリッドによって記述されたとされ、最も古いアルゴリズムの一つとしても知られています。この手法は、二つの数に対して繰り返し割り算を行い、その剰余を利用することで最大公約数を効率的に見つけ出すことができます。

基本的な考え方

二つの自然数 a と b (a ≧ b) が与えられたとき、a を b で割った余りを r とします。この時、a と b の最大公約数は、b と r の最大公約数と等しいという性質を利用します。つまり、gcd(a, b) = gcd(b, r) が成り立ちます。

この性質を利用し、b を r で割った余り、次に r をその余りで割った余り、というように、余りを求める計算を繰り返していきます。この過程を続けていくと、最終的に余りが 0 になります。この時、最後に割る数となったものが、元の二つの数の最大公約数となります。

具体例

例えば、1071 と 1029 の最大公約数を求める場合を考えます。

1. 1071 ÷ 1029 = 1 余り 42
2. 1029 ÷ 42 = 24 余り 21
3. 42 ÷ 21 = 2 余り 0

余りが0になった時の割る数である21が、1071と1029の最大公約数となります。

数学的な証明

ユークリッドの互除法の正しさは、以下の様に証明できます。

自然数 a, b (a ≠ 0) において、b を a で割ったときの商を q、余りを r とします。このとき、b = qa + r が成り立ちます。

ここで、d₀ を a と r の両方を割り切る自然数とします。このとき、d₀ は積 qa も割り切るため、和 qa + r、つまり b も割り切ります。したがって、a と r の公約数はすべて b と a の公約数となります。

逆に、d₁ を b と a の両方を割り切る自然数とします。このとき、d₁ は積 qa を割り切るため、差 b - qa、つまり r も割り切ります。したがって、b と a の公約数はすべて a と r の公約数となります。

これらのことから、b と a の公約数全体の集合は、a と r の公約数全体の集合と等しいことが分かります。特に、b と a の最大公約数は、a と r の最大公約数と一致します。

手続き的な記述

ユークリッドの互除法をアルゴリズムとして記述すると、以下のようになります。

1. 入力として m, n (m ≧ n) を受け取ります。
2. もし n = 0 なら、m を出力して終了します。
3. m を n で割った余りを新たな n とし、元の n を新たな m とします。
4. ステップ 2 に戻ります。

この手順は、剰余演算が定義されている環境であれば、整数環だけでなく、ユークリッド整域でも同様に適用できます。

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

拡張されたユークリッドの互除法では、二つの整数 m, n の最大公約数をgcd(m, n) と表すとき、mx + ny = gcd(m, n) を満たす整数 x, y の組を求めることができます。

例えば、先ほどの 1071 と 1029 の例では、gcd(1071, 1029) = 21 ですが、この21は、

21 = 1029 - 24 × 42
= 1029 - 24 × (1071 - 1 × 1029)
= -24 × 1071 + 25 × 1029

と変形できるため、x = -24, y = 25 が解の一つとなります。

特に、m と n が互いに素である場合（最大公約数が1の場合）、mx + ny = 1 の整数解 (x, y) が存在すれば、任意の整数 c に対して、mx + ny = c の整数解 (cx, cy) を見つけることができます。

一般的な表現

m = r₀, n = r₁ とするとき、ユークリッドの互除法の各ステップを繰り返すと、以下のような関係式が得られます。

r₀ = k₀r₁ + r₂ (0 < r₂ < r₁)
r₁ = k₁r₂ + r₃ (0 < r₃ < r₂)
r₂ = k₂r₃ + r₄ (0 < r₄ < r₃)
...
rₕ₋₁ = kₕ₋₁rₕ + 0

この過程は、行列を用いて表現することもでき、最終的に gcd(m, n) = rₕ となります。

計算量

ユークリッドの互除法の計算量は非常に効率的です。最悪の場合でも、小さい方の数の桁数の約5倍程度の割り算を繰り返すだけで、最大公約数に到達します（ラメの定理）。

このアルゴリズムは、素因数分解よりも遥かに高速に最大公約数を求めることができます。素因数分解は「困難な問題」と考えられていますが、最大公約数を求めることは「容易な問題」として知られています。

入力された二つの整数のうち、小さい方の整数 n の桁数を d とすると、ユークリッドの互除法では O(d) 回の除算で最大公約数が求められます。桁数 d は O(log n) であるため、計算量は O(log n) となります。

連分数との関係

ユークリッドの互除法の計算過程は、連分数展開と密接に関係しています。例えば、1071 と 1029 の最大公約数を求める過程は、

1071 = 1029 × 1 + 42,
1029 = 42 × 24 + 21,
42 = 21 × 2

と表せます。これを分数で表すと、

1071/1029 = 1 + 42/1029,
1029/42 = 24 + 21/42,
42/21 = 2

となり、最終的に 1071/1029 = 1 + 1/(24 + 1/2) という連分数で表現できます。このように、ユークリッドの互除法で得られた商は、有理数の連分数展開と一致します。

まとめ

ユークリッドの互除法は、古代から伝わるにも関わらず、現代でも非常に有効なアルゴリズムです。そのシンプルさと効率性から、さまざまな分野で応用されています。

もう一度検索