突然ですが皆さん、2つの数の最大公約数をちゃんと求めることができますか？

では、まずは小手調べ。12と18の最大公約数を求めてみてください。

—————

————

———

——

—

はい、答えは出ましたか？　正解は「6」です！

普通に習う最大公約数の求め方としては、

①まず小さい方の数の約数を求める→12の約数：1,2,3,4,6,12

②その中で18を割り切れるものを、大きい約数から順番に探す→18÷12=割り切れない、18÷6=割り切れる

③一番最初に割り切れた数が、二つの数の最大公約数→12と18の最大公約数は6

小6以上ならぜひ解けてほしいところですね（笑）

では、第2問！　1113と3763の最大公約数を求めてください。

制限時間は3分です！

—————

————

———

——

—

さて、どうですか？　解けましたか？

ではまずは、1113の約数を求めて……………………

はい、めちゃくちゃ大変ですね（笑）　これだけで3分が終わってしまいそうです。

2けたの整数の約数を求めるのであれば、慣れればそんなに難しくはありません。しかし、3桁以上ともなるとかなり骨の折れる作業になってしまいます。

それでは、この4桁どうしの整数の最大公約数をどのように求めるのか？　ここで登場するのが、タイトルにもある「ユークリッドの互除法」です。

タイトルだけ聞くとめちゃくちゃ難しそうですが、なんとこの法則は小学校4年生レベルの計算能力があれば使うことができます！

実際にやってみましょう。

①最大公約数を求めたい2つの整数について、大きい方を小さい方で割って余りを出す

→3763÷1113=3あまり424

②余りが出た場合、その式の「割る数（割り算の記号の右にある数字）」を余りで割る

→1113÷424=2あまり265

③割り切れるまで「前の式の割る数÷前の式の余り」の手順を繰り返す

→424÷265＝1あまり159、265÷159＝1あまり106、159÷106=1あまり53、106÷53＝2

④割り切れた時の式において、割る数になっているものが最大公約数

→1113と3763の最大公約数は、53

もちろん、この法則は何桁の数字でも使えます。なので、冒頭の「18と12の最大公約数」についても、

18÷12=1あまり6　12÷6=2　よって18と12の最大公約数は6

というように、簡単な割り算の計算のみで求めることができます。余裕があるなら、覚えておくといいかもしれませんね！

Tweet