ユークリッドの互除法（最大公約数を求める方法）とは何ですか？

———-
Answer
ユークリッドの互除法は、2つの自然数の最大公約数を求めるためのアルゴリズムです。最初に与えられた2つの自然数aとbに対して、aをbで割り、余りをrとします。このとき、aとbの最大公約数は、bとrの最大公約数に等しいことが示されます。そして、新たにbとrを用いて同じ手順を繰り返し、余りが0になるまで続けます。余りが0になったときのbが、2つの自然数aとbの最大公約数となります。このように、常に2つの自然数の小さい方を割ることを繰り返すことで、最大公約数を簡単に求めることができます。