\ フォローしてね /

高校「数学A」の「整数の性質:ユークリッドの互除法」分野の学び方

数学 Mathematics の語源は、ラテン語またはギリシア語の マテーマタ であり、学ばれるべきことども という意味だそうです。

数学者 ユークリッド (Euclid) はこのマテーマタを集大成し、古代ギリシア数学を代表する名著『原論』を編纂したそうです。『原論』に記述されているのが、まさに今回のテーマです。

ユークリッドの互除法を学習するポイント

ユークリッドの互除法の原理:世界最古のアルゴリズム

ある2つの数 a,b (a>b) の最大公約数 GCD を考えるとき、a,b ともに GCD で割り切れます。

となると、「a-b」 (あるいは何度も a-b が出来るのであれば、a÷b の余りr )の中にも GCD は含まれていることになります。この性質を使って、2つの数の最大公約数を手早く求めることが出来ます。

図を使って考える

この考え方をイメージ化すると、上記の図となります。一番大きな長方形の横辺を a 、縦辺を b とします。水色とベージュ色の正方形を最大公約数 GCD としています。

この正方形を求めるためには、まず短い方の辺を一辺とした正方形(青い正方形)を区切り取り、残った長方形でも、短い方の辺を一辺とした正方形(ピンクの正方形)を区切り取り、そのまま同じことを繰り返します。

その結果、残った長方形をぴったりと埋める正方形(緑の正方形)が現われたら、その正方形の一辺こそが最大公約数 GCD となります。

最大公約数の求め方

素因数分解を基にする場合

複数の自然数を素因数分解して、共通する素数を掛け算した結果が最大公約数になります。

素数とは、1とその自然数自身でしか割り切れない自然数のことです。ただし、1、は素数ではありまあいせん。
素因数分解の場合、対象となる素数の見当付けに手間取ることがあります。

ユークリッドの互除法を基にする場合

まず大きい方の自然数から小さい方の自然数を引きます。あるいは、大きい方の自然数を小さい方の自然数で割ります。

次に先に割った小さい方の数を余りで割ります。この繰返しで、最後に割り切れた時の割る数が求める最大公約数になります。

おわりに

筆者の場合、素因数分解を基にした最大公約数の求め方を先に学習していました。ユークリッドの互除法に出会って「目から鱗」の気持ちになったのは確かです。

(image by 足成)
(image by 筆者)

このライフレシピを書いた人

編集部にリクエスト!

「こんなライフレシピがほしい」や「ここがわかりにくかった」などをお送りください。