ユークリッドの互除法を用いて、48 と 18 の最大公約数を求めると、いくつになりますか？

ユークリッドの互除法は、gcd(a, b) = gcd(b, a mod b) という関係を使い、余りが 0 になるまで繰り返す方法です。48 と 18 の場合、gcd(48, 18) から 48 mod 18 = 12 なので gcd(18, 12) となり、18 mod 12 = 6 なので gcd(12, 6) となります。さらに 12 mod 6 = 0 となるため、最後の除数である 6 が最大公約数です。計算量は O(log(min(a, b))) と非常に高速です。