LCM vs GCD
LCM vs GCD compared — least common multiple vs greatest common divisor, formulas and uses, with a free calculator.
The GCD (greatest common divisor) is the largest number that divides two values; the LCM (least common multiple) is the smallest number both divide into. They are linked: LCM(a,b) × GCD(a,b) = a × b.
LCM vs GCD at a glance
| LCM | GCD | |
|---|---|---|
| Meaning | Smallest common multiple | Largest common divisor |
| Always | ≥ both numbers | ≤ both numbers |
| Used for | Adding fractions, cycles | Simplifying fractions |
When to use LCM
Use the LCM to find a common denominator or when two cycles re-align.
When to use GCD
Use the GCD to simplify a fraction or split into equal groups.
Tools for LCM & GCD
LCM・GCD計算機（最小公倍数・最大公約数）
任意個の整数の最大公約数と最小公倍数を、任意精度で正確に計算します。クライアント側だけで完結します。
ツールを開く分数計算機
分数の足し算・引き算・掛け算・割り算を自動約分付きで計算し、結果を小数と帯分数でも表示します。ブラウザ上でそのまま動作します。
ツールを開く素因数分解ビジュアライザー
因数分解ツリーで素因数分解をアニメーション表示 — 数を1ステップずつ素因数へ分解していきます。ブラウザだけで動作します。
ツールを開くユークリッドの互除法ビジュアライザー(GCD)
ユークリッドの互除法をアニメーションで表示 — (a, b) → (b, a mod b) という置き換えを繰り返しながら、2つの数の最大公約数(GCD)をステップごとに計算します。ブラウザ上でそのまま動作します。
ツールを開くLCM vs GCD
ユークリッドの互除法とは何ですか?
2つの整数の最大公約数(GCD)を求める方法で、大きい方の数を、それを小さい方の数で割った余りに置き換える操作を、余りが0になるまで繰り返します。
ユークリッドの互除法の時間計算量はどれくらいですか?
O(log min(a, b)) です。ステップ数は桁数に比例するため、非常に大きな数であっても極めて高速に計算できます。
なぜ gcd(a, b) = gcd(b, a mod b) が成り立つのですか?
a と b の公約数はすべて a mod b も割り切れます(その逆も同様です)。そのため、この置き換えを行っても公約数の集合、つまり最大公約数は変わりません。
GCDは何に使われますか?
分数の約分、モジュラー算術、拡張ユークリッドの互除法(モジュラー逆数、RSA)、そして lcm(a,b) = a·b / gcd(a,b) の式による最小公倍数の計算などに使われます。