RSSを登録する
ある2つの数の最大公約数（GCD）を考えるとき、2つの数はその最大公約数で割り切れるという関係において合同ですから、合同式の定義から、両数の差（あるいは何度も引けるのであれば一方を一方で割った余り）の中にもそのGCDは含まれています。ユークリッドの互除法は、割り算の余りのこの性質を使って、2つの数の最大公約数を手早く求める手法で、ユークリッドは幾何の原論と同じ、あのユークリッドです。
最大公約数を求めるとき、通常であれば2つの数を眺め、偶数かどうかからはじまって、倍数の判定法も活用しつつ、共通で割れそうな数を当てずっぽうで探しながら細切れに刻んでいく、というやり方をします。ですが、たとえば以下のようなケースでは、一見した限りではうまく最初の切り口がつかめません。
ユークリッドの互除法は、こういう場合でも、確実かつ効率よくGCDにたどりつける手法です。
やり方としては、まず大きい方の数から小さい数を引き（あるいは割り）ます。すると、差（余り）の中にもGCDがいますので、今度は、先に割った小さい数の方を余りで割る、ということを繰り返して追い込んでいき、最後に完全に割り切れたら、その数が求めるGCD、という手順です。
このとき、前段の元数を割り数で割ったときのGCDと、その割り数を余りで割り直したときのGCDはほんとうに同じ値なのか、ということは追って確認しますが、考え方の原理は、よく次のような正方形の図形を使った直観的な説明がされています。
2つの数を長方形の辺の長さに取ると、両数の公約数は、長方形の全体をぴったりすき間なく敷きつめる正方形で表すことができます。よってこの、長方形を敷きつめる正方形のうちの最も大きなものがGCD・最大公約数です。
この正方形を求めるためには、まず短い方の辺を単位にできるだけ大きな正方形を取り除き、残った長方形にも同じことを繰り返します。その結果、ハンパな余り長方形をぴったり埋めることができる正方形が現れれば、その正方形は、隣合う前工程のより大きな正方形もすき間なく埋めることができ、その上も、とたどって、元の長方形全体をぴったり敷きつめることのできる正方形ということになります。また、これより大きな正方形で同じようにできるものが存在しないことも、視覚的に把握できます。
ユークリッドの互除法の英語の用語に出てくる「アルゴリズム」とは、あれこれ考えなくても機械的に実行すれば誰でも結果が出せる計算の手順のことです。考えなくてもいいので、文字通り「機械（コンピュータ）」にそのまま実行させることもできます。
ユークリッドの互除法は、紀元前から知られている世界最古のアルゴリズムと言われる一方、剰余演算とともに現代の暗号技術の中でも中核的に用いられている考え方で、最高齢にして今でも現役バリバリで活躍中という、「スーパーおじいちゃん」みたいな、スゴいアルゴリズムです。
