ユークリッドの互除法

ユークリッドの互除法とは、2つの自然数の最大公約数を求めるアルゴリズムである。

概要

最大公約数を求めたい2つの整数をm, n（どちらか一方が0以上の整数、もう一方が正の整数）とすると、以下のような手順で、mとnの最大公約数を求めることができる。

1. n = 0の場合、mを最大公約数として終了する。n > 0の場合、2.へ進む。
2. m ÷ nの余りをrとし、mにn、nにrを代入する。
3. 1.へ戻る。

剰余の代わりに減算を用いる方法もあるが、両者の間に本質的な差異は何もない。

ユークリッドの互除法は最古のアルゴリズムとしても有名だが、優れたアルゴリズムと言われる所以は手数の少なさにある。アルゴリズムを終了するのに十分な手数は、nの桁数に比例するのである。具体的に言うと、nの10進桁数の5倍だけ行うまでに、結果がわかる。紀元前の時代にここまで優れたアルゴリズムが存在したことは注目に値する。

例

728と693の最大公約数を求める。

1. 693 > 0 より、728 ÷ 693 → 1 あまり 35
2. 35 > 0 より、693 ÷ 35 → 19 あまり 28
3. 28 > 0 より、35 ÷ 28 → 1 あまり 7
4. 7 > 0 より、28 ÷ 7 → 4 あまり 0

よって、728と693の最大公約数は、7。

プログラミング言語での実装

Dによる実装

uint getGCD(uint a, uint b) {
 if(a < b)
 return getGCD(b, a);
 int r = a % b;
 if(r == 0)
 return b;
 return getGCD(b, r);
}

Cによる実装

int G(a,b){return a<b?G(b,a):(b>0?G(b,a%b):a);}

Lispによる実装

(define (gcd a b)
　　　　　　(if (= b 0)
               a
              (gcd b (remainder a b))))

関連動画

高校数学の範囲での証明方法である。

関連項目

• アルゴリズム
• プログラミング関連用語の一覧