【数の構成】ユークリッドの互除法 | 大人が学び直す数学合同式とともに、「余り付き割り算」と縁の深い計算テクニックに、ユークリッドの互除法（Euclidean algorithm） があります。 ある2つの数の最大公約数（GCD）を考えるとき、2つの数はその最大公約数で割り切れるという関係において合同ですから、合同式の定義から、両数の差（あるいは何度も引けるのであれば一方を一方で割った余り）の中にもそのGCDは含まれています。ユークリッドの互除法は、割り算の余りのこの性質を使って、2つの数の最大公約数を手早く求める手法で、ユークリッドは幾何の原論と同じ、あのユークリッドです。 最大公約数を求めるとき、通常であれば2つの数を眺め、偶数かどうかからはじまって、倍数の判定法も活用しつつ、共通で割れそうな数を当てずっぽうで探しながら細切れに刻んでいく、というやり方をします。ですが、たとえば以下のようなケースでは、一見した限りではうまく最初の切り口がつか
