（改題）本来、Euclidの互除法は図形的に捉えるものだ ～ユークリッドの互除法の図形的説明～

問題　縦4370mm、横7130mmの長方形の部屋を同じ大きさの正方形のタイルカーペットで敷き詰めたいと思います。敷き詰められる正方形で最大のものは、一辺が何mmのタイルカーペットですか。

読者の中には、「最大公約数を求めればよい」と即答された方もいると思いますが、では答えはというと簡単ではないと思います。

素因数を見つけるだけでも大変なので、こういうときにはEuclid(ユークリッド)の互除法が有効です。その仕組みを説明したいので、数を簡単にします。

縦６ｍと横14ｍとして説明します。このとき、敷き詰められる最大の正方形の候補は、一辺が６ｍの正方形ですね。それを表現したのが下図です。

一辺が６ｍの正方形で敷き詰められないことは分かりました。

ここで、《もしも赤い部分が正方形で敷き詰められたら、２つの正方形もその正方形で敷き詰められますね。また、赤い部分が正方形で敷き詰められなかったら、２つの正方形もその正方形では敷き詰められません。だから、赤い部分の長方形を出来るだけ大きい正方形で敷き詰めることが出来れば全体の長方形もその正方形で敷き詰められます》。

その最大の正方形の候補は、一辺が２ｍの正方形です。６－２－２－２＝０なので、一辺が２ｍの正方形で敷き詰められます。▮

上の《　》の部分が本質的な部分で、それを繰り返し用いたものがEuclidの互除法なのです。この考え方であれば、小学生でも気づいている子がいると思います。

では、もう少し値を大きくし、縦21㎝、横51㎝とします。これを図で表現すると

です。式で表現すると、

51-21-21=9（←51-21×2=9）※一辺が21㎝はダメ
21-9-9=3（←21-9×2=3）※一辺が９㎝もダメ
9-3-3-3=0（←9-3×3=0）※一辺が３㎝でうまくいく
よって、一辺が3㎝の正方形で敷き詰められます。▮

では、最初に挙げた問題を解いてみます。
7130-4370=2760　※一辺が4370mmはダメ
4370-2760=1610　※一辺が2760mmもダメ
2760-1610=1150　※一辺が1610mmもダメ
1610-1150=460　※一辺が1150mmもダメ
1150-460-460=230（←1150-460×2=230）　※一辺が460mmもダメ
460-230-230=0（←460-230×2=0）　※一辺が230mmでうまくいく
よって、一辺が230mmのタイルカーペットで敷き詰められます。▮

上の２つの計算は、次のようにしています。

ユークリッドの互除法の計算の仕方は他にもありますが、仕組みは同じです。▢

※計算の仕方は、動画だと分かりやすいと思います。(2021.4.18 9:33以降視聴可)