最大公約数・最小公倍数 計算機

2つ以上の整数の最大公約数(GCD)と最小公倍数(LCM)を計算。ユークリッドの互除法の計算ステップやすだれ算の途中式を完全可視化。

最大公約数・最小公倍数 計算機
例題入力:
GCD と LCM の計算結果
最大公約数 (GCD)
6
最小公倍数 (LCM)
36
ユークリッドの互除法による計算ステップ

    最大公約数(GCD)と最小公倍数(LCM)の基本概念

    整数論において最も基本的かつ強力な2大指標が最大公約数(Greatest Common Divisor, GCD)と最小公倍数(Least Common Multiple, LCM)です。

    • 最大公約数(GCD): 2つ以上の整数に共通する約数(公約数)の中で、最も大きい数値。分数の「約分」において一発で既約分数にする際に利用されます。
    • 最小公倍数(LCM): 2つ以上の整数に共通する倍数(公倍数)の中で、最も小さい正の数値。分数の「通分」において共通分母を最小にする際に利用されます。

    最速アルゴリズム:ユークリッドの互除法

    2つの数が 1071 と 1029 のように桁数が大きい場合、素因数分解を行うのは大変です。そこで紀元前から受け継がれる世界最古のアルゴリズム「ユークリッドの互除法(Euclidean Algorithm)」を用います。

    ユークリッドの互除法の原理
    \[ A = B \times Q + R \implies \gcd(A, B) = \gcd(B, R) \]

    「2つの数 A と B の最大公約数は、B と “AをBで割った余りR” の最大公約数に等しい」という性質を利用し、余りが 0 になるまで割り算を繰り返すだけで、確実にGCDが導かれます。

    GCDとLCMの美しい恒等式

    正の整数 $a$ と $b$ の間には、常に次の絶対的な関係式が成り立ちます。

    積と公約数・公倍数の関係
    \[ a \times b = \gcd(a, b) \times \text{lcm}(a, b) \]

    したがって、ユークリッドの互除法で最大公約数 $\gcd(a, b)$ を求めてしまえば、最小公倍数は $\text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$ の割り算1回で瞬時に計算できるのです。

    よくある質問(FAQ)

    2つの整数の最大公約数が 1 である関係を「互いに素(coprime)」と呼びます。例えば 15 と 28 はそれぞれ合成数ですが、共通の約数が 1 しかないため互いに素です。

    結合法則が成り立つため、まず2つの数のGCDを求め、その結果と3つ目の数のGCDを求める、という手順を順次繰り返すことで何個の整数でも計算可能です(例: gcd(A, B, C) = gcd(gcd(A, B), C))。

    すべての正の整数には共通の約数として「1」が存在するため、最小公約数は常に 1 となり、数学的な議論の対象にならないためです。

    はい、正の数に直して絶対値で計算すれば全く同様に適用できます。

    画像リサイズ時のアスペクト比計算、画面描画のリフレッシュレート同期、暗号理論(RSA暗号の鍵生成)、時計の歯車比の設計など、工学分野の根幹で日常的に使われています。