ユークリッドの互除法【Euclidean algorithm】

概要

ユークリッドの互除法（Euclidean algorithm）とは、二つの自然数の最大公約数を求める計算手順(アルゴリズム)の一つ。古代ギリシャの数学者ユークリッド(Euclid/エウクレイデス)の発見した古典的な手法で、紀元前4世紀頃に編纂された「原論」に掲載されており、記録に残る最古のアルゴリズムとも言われる。

二数の最大公約数は両者とも割り切ることができる自然数（公約数）のうち最大のものだが、これは大きい方を小さい方で割った余り（剰余）と小さい方との最大公約数に等しいという性質があり、これを利用して効率的に算出する。

aとbの2つの数（a≧bとする）の最大公約数を求める場合、まずaをbで割った余りb'を求める。次に、b'をaで割った余りa'を求める。さらに、a'をb'で割った余りを求め…と交互に余り同士の割り算を繰り返し、初めて割り切れた（余りが0になった）ときの除数（割る方の数、小さい方の数）がaとbの最大公約数である。

例えば、119と49の最大公約数をこの手順で求めると、119÷49＝2・・・35 → 49÷35＝1・・・14 → 35÷14＝2・・・7 → 14÷7＝2・・・0 となり、最後の除算の除数である7が両者の最大公約数であるとわかる。

(2018.12.17更新)