当サイトのコンテンツは受験算数アーカイブスの「算数学」コンテンツへと移管いたしました.

2011/01/02

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

 アーカイブ:「数の性質」

二つの数の最大公約数を求める・・・これは中学受験算数ではかなり頻度の高い計算です.
通常はすだれ算を使えば比較的簡単に求めることができます.しかし,例えば「221と323の最大公約数」を求めなくてはならなくなったとき,これはすだれ算でもなかなか計算することができません.
答えは17なのですが,これをすだれ算で出そうとすると,素数を小さい順に当てはめていくしかありません.2数の公約数が大きな素数である場合はその数を求めるのは簡単なことではないのです.

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


■ ユークリッド互除法の計算方法

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

a ÷ b = c・・・d

b ÷ d = e・・・f

d ÷ f = g・・・h




と順次計算をすすめると




p ÷ q = r・・・s

q ÷ s = t

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



~221と323の場合~

323 ÷ 221 = 1・・・102

221 ÷ 102 = 2・・・17

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

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


関連情報:
ユークリッド互除法を図で考える