数学A
2つの数の最大公約数(GCD)を、素早く確実に求める方法がユークリッドの互除法だよ。長方形を「入るかぎり大きい正方形」で切り取っていくと、最後に残った正方形の一辺が答え。前に学んだ約数・倍数の考えを土台に、「あまりで次を割る」という手続きの意味を、図でまるごとつかむ単元なんだ。
横 ・縦 の長方形を用意して、入るかぎり大きい正方形で切り取っていく。まず一辺 の正方形が つ取れて、残りは の帯。その帯には一辺 の正方形がちょうど つ、あまりなくおさまる。最後に敷きつめた正方形の一辺 が、 と の最大公約数(GCD)だ。
「大きい正方形で切って、残った長方形にまた最大の正方形を」をくり返し、あまりが出なくなったら終わり。前に学んだ約数・倍数の「ぴったり敷きつめる」感覚が、ここでは2つの数の共通のものさし(最大公約数)を見つける操作になっているんだ。
この正方形の切り取りは、数の割り算とぴったり対応している。(一辺 の正方形 つ、あまり )、(一辺 の正方形 つ、あまり )。あまりが になったときの「割る数」 が答えだ。図の「残った長方形にまた正方形を」が、数の「あまりで次を割る」に当たる。
だから互除法は、「大きい数を小さい数で割り、出たあまりで今度は割る側を割る」をくり返し、あまりが になった瞬間の割る数を答えにする手続きになる。素因数分解しにくい大きな数どうしでも、この反復だけで最大公約数にたどり着ける。これが互除法の強さで、この先の不定方程式を解く土台にもなるよ。
互除法でいちばん多い取りちがえが、答えにする数をまちがえること。最後のあまり()を答えにしてしまったり、途中のあまりを答えにしてしまったりしやすい。正しくは、あまりが になった、その割り算で「割る数」になっていた数が最大公約数だ。 なら、あまり の直前で割る数だった が答え。図でいえば、最後にぴったり敷きつめた正方形の一辺にあたる。「あまり の割り算の、割る数を読む」と手順で覚えておこう。
互除法を「大きい数を小さい数で割り、あまりでまた割る」という手順だけで丸暗記すると、なぜそれで最大公約数が出るのか分からず、応用がきかなくなる。図にもどると腑に落ちる。 も も、共通の正方形で敷きつめられるなら、その正方形は残りの の帯も敷きつめられるはず。だから「もとの2数の公約数」と「小さいほうとあまりの公約数」は同じになり、数を小さくしながら共通のものさしを探せる。最後まで敷きつめきれた正方形の一辺が、2数に共通する「いちばん大きいものさし」＝最大公約数だ。手続きの裏にこの図があると、なぜ答えが出るのかを自分の言葉で説明できるようになるよ。
最大公約数を求める方法は互除法だけではなく、 つの数をそれぞれ素因数分解して共通部分を取る、というやり方もある。小さな数どうしなら素因数分解のほうが速いことも多い。でも数が大きくなると、素因数分解そのものが一気に難しくなる。 と の最大公約数を、素因数分解で求めるのは大変だ。互除法のすごいところは、素因数分解をまったくしなくても、割り算のくり返しだけで、どんなに大きな数でも確実に答えにたどり着けること。「小さい数は素因数分解、大きい数は互除法」と、道具を状況で使い分けられるようになると、整数の問題での手数がぐっと減るよ。前に学んだ約数・倍数の素因数分解と、この互除法は、同じ最大公約数を別の道から求めているんだ。どちらの道を通っても答えが一致するのを一度確かめておくと、互除法が本当に最大公約数を出しているのだと安心できるよ。