ユークリッドの互除法

この頁は既定のパラメータ(a = 12, b = 18)での解答例です。

解答

• $$\gcd\left(12,\ 18\right) = 6$$

解説(ステップ)

1. 1ユークリッドの互除法: 割った余りで置き換えを繰り返します
   $$18 \div 12 = 1 \text{ 余り } 6\\12 \div 6 = 2 \text{ 余り } 0\\$$
2. 2余りが0になったときの割る数が最大公約数です
   $$\gcd(12, 18) = 6$$

この解法は人手で実装し、単体テストで検証しています(自動生成の答案ではありません)。