ユークリッド互除法を利用して最大公約数を求める

二つの数の最大公約数を求める・・・これは中学受験算数ではかなり頻度の高い計算です．

通常はすだれ算を使えば比較的簡単に求めることができます（すだれ算のやり方についてはこちらのページ（すだれ算の基本）を参照してください）．しかし，例えば「221と323の最大公約数」を求めなくてはならなくなったとき，これはすだれ算でもなかなか計算することができません．

答えは17なのですが，これをすだれ算で出そうとすると，素数を小さい順に当てはめていくしかありません．２数の公約数が大きな素数である場合はその数を求めるのは簡単なことではないのです．

ところが今回紹介する「ユークリッド互除法」を使うと，どんな２数であっても確実に最大公約数を求めることができるようになります．

aとbの２数の最大公約数を求めたい場合の計算方法は以下の通りです．

a ÷ b ＝ c ・・・ d

b ÷ d ＝ e ・・・ f

d ÷ f ＝ g ・・・ h
・
・
・
と順次計算をすすめると
・
・
・
p ÷ q ＝ r ・・・ s

q ÷ s ＝ t

このように最終的には必ず割り切ることができます．
そしてこの時，最後の計算に現れる「ｓ」がaとbの最大公約数なのです．

では具体的に221と323の最大公約数をユークリッド互除法で求めてみましょう．

323 ÷ 221 ＝ 1・・・102

221 ÷ 102 ＝ 2・・・17

102 ÷ 17 ＝ 6 (割り切れた)

よって最大公約数は17と求まります．