最大公約数（GCD）とは、2つ以上の整数を割り切れる最大の数のことです。12と18の場合、割り切れる数はどちらも1、2、3、6なので、最大公約数は6です。最大公約数は、最大公約数とも呼ばれます。

ユークリッドの互除法は、最大公約数を効率的に求める方法です。大きい数を小さい数で割り、大きい数を余りで置き換え、余りがゼロになるまで繰り返します。最後にゼロでない余りが最大公約数です。この方法は2000年以上前から存在し、現在でもコンピュータサイエンスで用いられています。

最大公約数 (GCD) は分数を簡約化します。分子と分母をそれぞれの最大公約数で割ると、分数は既約分数になります。また、モジュラー算術、暗号、数論にも登場します。最小公倍数は、LCM(a, b) = a × b / GCD(a, b) という式で最大公約数と関連付けられます。

• 整数を割り切る最大の数
• ユークリッドの互除法によって発見された
• 分数を簡略化するために使用されます
• 簡単な公式で最小公倍数と関連付けられる