仕組み
最大公約数(GCD)はユークリッドの互除法で求めます。大きい数を小さい数で割った余りに置き換える操作を、余りが0になるまで繰り返します。3つ以上の数は2つずつ順に計算します。
最小公倍数(LCM)は最大公約数から求めます。lcm(a, b) = |a × b| ÷ gcd(a, b) を2つずつ適用します。すべて正確な整数で計算するので、30桁の数でも誤差はありません。
ユークリッドの互除法の手順
1071 と 462 の例:各行で前の割る数を余りで割り、最後に0でない余りが最大公約数です。
- 1071 = 2 × 462 + 147
- 462 = 3 × 147 + 21
- 147 = 7 × 21 + 0 → gcd = 21
gcd(a, b) = gcd(b, a mod b) · lcm(a, b) = |a × b| ÷ gcd(a, b)
こんなときに使います
- 最大公約数:分数の約分。18/24 を最大公約数 6 で割ると 3/4。
- 最小公倍数:通分や、周期の違うできごとが再び重なる日(4日ごと・6日ごと → 12日ごと)。
- 最大公約数:タイルや列、グループを余りなく同じ大きさに分ける。
ポイント
- 最大公約数が 1 なら互いに素です。8 と 9 のように両方が合成数でも互いに素になりえます。
- 2つの正の整数では gcd(a, b) × lcm(a, b) = a × b なので検算に便利です。
- 0 も入力できます。gcd(a, 0) = a で、0 を含む最小公倍数は 0 です。
基準と出典
- ユークリッドの互除法 · NIST Dictionary of Algorithms and Data Structures
- 最小公倍数 · NIST Dictionary of Algorithms and Data Structures
最終確認 2026年10月20日
よくある質問
最大公約数と最小公倍数の違いは?
最大公約数はすべての数を割り切る最大の数、最小公倍数はすべての数で割り切れる最小の数です。12 と 18 なら最大公約数は 6、最小公倍数は 36 です。
GCD、GCF、HCF は同じですか?
はい。どれも最大公約数を表す英語の呼び方です。
数はいくつまで入力できますか?
個数の制限はなく、2つずつ順に計算します。素因数分解は最初の12個まで表示します。