ユークリッドの互除法とは、2つの自然数の最大公約数を効率的に求める古典的なアルゴリズムのことです。
以下は、ユークリッドの互除法の手順です。
1. 2つの自然数\(a\)と\(b\)を用意します（ただし、\(a>b\)とします）。
2. \(a\)を\(b\)で割った余り\(r\)を求めます。
3. \(b\)と\(r\)で手順2を繰り返します。
4. 余りが0になった時の割る数\(r\)が\(a\)と\(b\)の最大公約数です。
例えば、252と105の最大公約数を求める場合、次のように計算します。
1. 252を105で割ると、余りは42。
2. 105を42で割ると、余りは21。
3. 42を21で割ると、余りは0。
よって、252と105の最大公約数は21です。