ユークリッドの互除法

本記事では，最大公約数を求めるアルゴリズムであるユークリッドの互除法の解説をしたいと思います．
この記事では$x$，$y$の最大公約数を$(x, y)$と表記します．

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

ユークリッドの互除法(Euclidean Algorithm)は，2つの自然数の最大公約数を求めるアルゴリズム¹処理手順，計算手順です．世界最古のアルゴリズムとして知られており，ユークリッドの『原論』の中にその記述があります²Wikipediaの注釈に該当箇所の引用あり．．アルゴリズムについて纏められたクヌース³Donald Ervin Knuthの著書”The Art of Computer Programming”においても，最初に取り上げられるアルゴリズムです．

最大公約数を求めるにあたり，素因数分解をすれば良いと考えるかもしれませんが，大きな数の場合は，素因数分解に時間がかかり⁴試しに116301の素因数分解をしてみましょう．，ユークリッドの互除法の方が早く最大公約数を見つけることができます⁵人間が計算する場合に限らず，コンピュータの計算量としても．．

また，少し工夫をすれば，2つの整数の最大公約数を求めることもできます．

ユークリッドの互除法のアルゴリズム

それでは，自然数$m$，$n$の最大公約数$(m,n)$を求めるアルゴリズムを書いていきます．

ユークリッドの互除法
入力：2つの自然数$m$，$n$
出力：最大公約数$(m,n)$

手順1．
$m \leqq n$であれば，$m$と$n$の値を入れ替える．（$m \geqq n$とする）
手順2．
$n=0$であれば，$m$を最大公約数として出力する．
$n \neq 0$ならば，手順3へ進む．
手順3．
$m \div n$の余りを求め，$m$に$n$の値を代入，$n$に先ほど求めた余りを代入して，手順2に戻る．

手順を多少入れ替えても良さそうに見えますが，0による除算の回避，$(0,0) = 0$となることを考えると，この手順しかありません．

ユークリッドの互除法の使用例

例として，4686と6954の最大公約数を，ユークリッドの互除法で求めます．

入力：$m = 4686$，$n = 6954$
手順1
$m \leqq n$なので，$m$と$n$を入れ替える．
$m = 6954$，$n = 4686$
手順2（1回目）
$n = 4686 \neq 0$なので，手順3へ進む．
手順3（1回目）
$6954 \div 4686 = 1 \cdots 2268$
$m = 4686$，$n = 2268$として手順2へ戻る．
手順2（2回目）
$n = 2268 \neq 0$なので，手順3へ進む．
手順3（2回目）
$4686 \div 2268 = 2 \cdots 150$
$m = 2268$，$n = 150$として手順2へ戻る．
手順2（3回目）
$n = 150 \neq 0$なので，手順3へ進む．
手順3（3回目）
$2268 \div 150 = 15 \cdots 18$
$m = 150$，$n = 18$として手順2へ戻る．
手順2（4回目）
$n = 18 \neq 0$なので，手順3へ進む．
手順3（4回目）
$150 \div 18 = 8 \cdots 6$
$m = 18$，$n = 6$として手順2へ戻る．
手順2（5回目）
$n = 6 \neq 0$なので，手順3へ進む．
手順3（5回目）
$18 \div 6 = 3$
$m = 6$，$n = 0$として手順2へ戻る．
手順2（6回目）
$n = 0$なので，$m = 6$を最大公約数として出力．
出力：$(4686, 6954) = 6$

手計算だと少し時間がかかってしまいましたが，コンピュータならば，素因数分解をするよりも早く解に辿り着くはずです．

ユークリッドの互除法の理論

ユークリッドの互除法のアルゴリズムは分かりました．
では，なぜこのアルゴリズムで最大公約数が求められるのでしょうか．
その原理となる命題を証明してみましょう．

命題．
整数$a$，$b$に関して，$(a, b) = (a-qb, b)　(qは整数)$ が成り立つ．

証明．
$(a, b) = m$，$a-qb = a^{\prime}$とおく．
$m$は$a$，$b$の約数なので，$m$は$a-qb$の約数である．また，$a = a^{\prime} + qb$より，$(a-qb, b)$は$(a, b)$の約数である．
$(a-qb, b)$と$(a, b)$は互いに約数となるので，
$(a, b) = (a-qb, b)$

ユークリッドの互除法では，$(a, b) = (a-qb, b)$の$a-qb$が $a$を$b$で割った余りにあたります．この等式を繰り返して，割り切れるところまで続けているのがユークリッドの互除法です．

ユークリッドの互除法のプログラム

せっかくアルゴリズムについて学んだのですから，最後にユークリッドの互除法のコードを書いてみましょう．

まずはPythonでコーディングをしました．入力は自然数のみを想定しています．

def gcd(m, n):
    # 手順1
    if m < n:
        l = m
        m = n
        n = l
    # 手順2 n=0なら終了
    if n == 0:
        return m
    # 手順3 n=0ではない場合，nと余りで手順2に戻る
    else:
        rem = m % n
        m = n
        n = rem
        return gcd(m, n)

ちなみに，関数を動かすと以下のようになります．

print(gcd(4686, 6954))

6

負の数を入力するとエラーを吐くので，入力を整数に拡張してみましょう．

def gcd(m, n):
    # 手順1　絶対値を取って入力を非負に変換
    if abs(m) < abs(n):
        l = abs(m)
        m = abs(n)
        n = l
    # 手順2 n=0なら終了
    if n == 0:
        return m
    # 手順3 n=0ではない場合，nと余りで手順2に戻る
    else:
        rem = m % n
        m = n
        n = rem
        return gcd(m, n)

せっかくなのでProlog⁶「プログラミング言語は1種類書けるようになれば，他の言語の学習が容易になる」という神話を壊してくれる素敵な言語です．述語論理をそのまま実装できる変わった性質を持っており，他の言語のプログラミング経験者でも混乱します．という言語でもユークリッドの互除法を実装してみました！ちなみに入力は整数に対応しています．

gcd(0, X, Gcd) :- Gcd is abs(X).
gcd(X, Y, Gcd) :- X =\= 0, Rem is Y mod X, gcd(Rem, X, Gcd).

清々しいほど短くて良いですね！さっそく実行してみましょう！

?- consult('gcd.pl').
true.

?- gcd(4686, 6954, X).
X = 6 .

ちなみに，自然数のみを入力とする場合は，以下のようなコードで問題ありません．

gcd(0, Gcd, Gcd) .
gcd(X, Y, Gcd) :- X =\= 0, Rem is Y mod X, gcd(Rem, X, Gcd).

参考文献

Donald E. Knuth “The Art of Computer Programming” Volume1

ユークリッドの互除法 – Wikipedia (2022年3月16日閲覧)
https://ja.wikipedia.org/wiki/ユークリッドの互除法#手続き的記述

高木貞治『初等整数論講義 第2版』共立出版．1971．

Max Bramer “Logic Programming with Prolog” Springer．2005．
(Prologを思い出すために読みました)

「勝手気ままに高校数学」シリーズ一覧へ