初学者向けの解説：ユークリッドの互除法ってなに？

ユークリッドの互除法（ごじょほう）とは、2つの数の「最大公約数（一番大きな共通の割り切れる数）」を簡単に見つけるための計算方法です。

この画面では、その計算を「長方形を正方形で敷き詰めるパズル」として目で見てわかるようにしています。

• まず、入力した縦と横の長さで「長方形」を作ります。
• その中に、「作れる限り一番大きな正方形」を置いていきます。
• もし隙間（小さな長方形）が残ったら、その残った隙間に対して、また同じように一番大きな正方形を置いていきます。
• これを繰り返し、最後に隙間なくピッタリ敷き詰められた時の、一番小さな正方形の「一辺の長さ」が、最初の2つの数の最大公約数になります！

数字の計算だけだと難しく見えますが、図形にすると「余った部分を切り取っていく」というシンプルなルールであることが分かります。