最大公約数 最小公倍数 計算｜複数値のGCD・LCM・素因数分解を一括算出

計算式と基本定義

ユークリッドの互除法：GCD(a, b) = GCD(b, a mod b)、b=0でGCD=a
LCM(a, b) = a × b ÷ GCD(a, b)
複数値：GCD(a, b, c) = GCD(GCD(a, b), c)
LCM(a, b, c) = LCM(LCM(a, b), c)
GCD(a, b) × LCM(a, b) = a × b（2数のみ）

最大公約数 (Greatest Common Divisor, GCD) は、2つ以上の整数を共通で割り切る最大の正整数です。最小公倍数 (Least Common Multiple, LCM) はそれらすべての倍数となる最小の正整数。GCDは分数の約分・等間隔配置に、LCMは分数の通分・周期問題に使われます。

例：12, 18, 30 の場合。GCD = 6（すべてを6で割り切れる最大値）、LCM = 180（3数すべての倍数となる最小値）。12 = 2²×3、18 = 2×3²、30 = 2×3×5 と素因数分解して、共通素因数の最低次数がGCD、全素因数の最高次数がLCMになります。

ユークリッドの互除法

ユークリッドの互除法は、紀元前300年頃のギリシャの数学者ユークリッド（エウクレイデス）が『原論』第7巻に記した、2数のGCDを高速に求めるアルゴリズムです。2300年経った現代でも整数論・暗号理論の基礎として現役で使われています。

手順

GCD(1071, 462) を求める例：

1071 = 462 × 2 + 147
462 = 147 × 3 + 21
147 = 21 × 7 + 0 ← 余り0でGCD = 21

「大きい数を小さい数で割り、余りで割り直す」を繰り返し、余りが0になった時の除数がGCD。試し割りに比べ計算回数が対数的（O(log n)）で、100桁の整数でも数百回で終了します。

拡張ユークリッド互除法

拡張ユークリッド互除法は、GCD(a, b) = ax + by となる整数 x, y を同時に求めるアルゴリズム。この (x, y) はベズーの等式の解と呼ばれ、RSA暗号の秘密鍵計算（モジュラ逆元）の中核です。競技プログラミング・暗号ライブラリの必須実装。

素因数分解と算術の基本定理

算術の基本定理（素因数分解の一意性）：1より大きいすべての整数は、素数の積として一意に表せます。例：60 = 2² × 3 × 5、100 = 2² × 5²、720 = 2⁴ × 3² × 5。

試し割り法

2, 3, 5, 7... と小さい素数から順に割り、割り切れるだけ割る古典的手法。√n までの素数を試せば十分（それより大きい素数の因子は最大1つ）。n = 10⁹ でも約3万回の試し割りで完了し、実用的です。

大きな数の素因数分解の困難性

100桁以上の数の素因数分解は、宇宙年齢（138億年）以上かかるとされる計算量的難問。この困難性が、RSA暗号の安全性の根拠になっています。効率的な古典アルゴリズムとして楕円曲線法・二次篩法・数体篩法が知られ、量子コンピュータのショアのアルゴリズムは理論上多項式時間で解けます。

素因数分解でGCD・LCMを求める

GCD = 各素因数の指数の最小値を取る
LCM = 各素因数の指数の最大値を取る

例：a = 60 = 2²×3×5、b = 84 = 2²×3×7 → GCD = 2²×3 = 12、LCM = 2²×3×5×7 = 420。

約数と約数の個数

約数とは、ある整数を割り切る整数のこと。約数の個数と総和は、素因数分解から公式で求まります。

n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ のとき
約数の個数 τ(n) = (a₁+1)(a₂+1)...(aₖ+1)
約数の総和 σ(n) = Π (p^(aᵢ+1) − 1)/(p − 1)

例：60 = 2²×3×5 → 約数の個数 = 3×2×2 = 12個、約数総和 = (2³−1)(3²−1)/(2)(5²−1)/(4)... = 168。

約数の総和が自分自身と等しい数を完全数と呼び、6・28・496・8128... と続きます。ユークリッドが「メルセンヌ素数から完全数を作る公式」を『原論』で示し、オイラーが「偶数完全数はこの形しかない」ことを証明しました。奇数完全数の存在は現在も未解決問題です。

分数の通分・約分への応用

分数計算はGCD・LCMの最重要応用分野です。小学5〜6年の算数の中核内容として文部科学省学習指導要領に位置付けられています。

約分（GCD使用）

分子と分母のGCDで割り、既約分数にする操作。
18/24 → GCD(18, 24) = 6 → 3/4
84/126 → GCD(84, 126) = 42 → 2/3

通分（LCM使用）

異分母の分数を、分母のLCMに合わせて統一する操作。
1/4 + 1/6 → LCM(4, 6) = 12 → 3/12 + 2/12 = 5/12
1/6 + 1/8 + 1/12 → LCM(6, 8, 12) = 24 → 4/24 + 3/24 + 2/24 = 9/24 = 3/8

よくある問題例

歯車・周期・等間隔配置

歯車の噛み合い

歯数14の歯車Aと歯数21の歯車Bが噛み合う場合。全ての歯が一度ずつ噛み合って初期位置に戻る歯数はLCM(14, 21) = 42。つまり歯車Aは3回転、歯車Bは2回転で初期状態に戻ります。この計算は自動車のギア設計、時計のムーブメント、機械式カウンタ設計で必須です。

惑星の会合周期

公転周期の異なる2惑星が同じ相対位置に来るまでの周期（会合周期）。地球（1年）と火星（1.88年）が会合するのは、シノディック周期の計算により約2.14年ごと。厳密には有理数近似でLCM的な計算をします。

等間隔配置

長さ120cm・180cm・240cmの3種類の板を、余りなく同じ長さに切る最大長 = GCD(120, 180, 240) = 60cm。工作、建築、フローリング施工でよく使う考え方です。

RSA暗号と整数論の応用

1977年に発表されたRSA暗号（Rivest-Shamir-Adleman）は、現代のインターネット通信（HTTPS/TLS）の基盤となる公開鍵暗号方式で、GCD・素因数分解の困難性を安全性の根拠にしています。

RSA鍵生成の概略

1. 大きな素数 p, q（各1024ビット以上）を選ぶ
2. n = p × q（法）、φ(n) = (p−1)(q−1)（オイラーのトーシェント）を計算
3. e を「GCD(e, φ(n)) = 1」となる整数から選ぶ（公開鍵）
4. 拡張ユークリッド互除法で d ≡ e⁻¹ (mod φ(n)) を計算（秘密鍵）

ここで互いに素の判定（GCD=1）と拡張ユークリッド互除法が本質的に使われます。素因数分解の困難性から、公開鍵 (n, e) を知っていても p, q を復元できず、秘密鍵 d は攻撃者にはわからない、という構造。

Diffie-Hellman鍵交換・楕円曲線暗号

その他、Diffie-Hellman鍵交換、楕円曲線暗号（ECC）、ゼロ知識証明などの現代暗号技術も整数論を土台にしています。IPA（情報処理推進機構）の暗号技術ガイドラインでこれらの技術仕様が公表されています。

計算量と実装（Python・JavaScript）

ユークリッド互除法はO(log min(a, b))の高速アルゴリズムで、100桁の数でも数百回で終了します。試し割りのO(min(a, b))とは比較にならない効率です。

Python実装

from math import gcd, lcm
gcd(12, 18) # 6
lcm(4, 6) # 12（Python 3.9+）
# 拡張版
def extgcd(a, b):
  if b == 0: return a, 1, 0
  g, x, y = extgcd(b, a % b)
  return g, y, x - (a // b) * y

JavaScript実装

const gcd = (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b);
const lcm = (a, b) => Math.abs(a * b) / gcd(a, b);

教育・実務での応用

整数論の歴史と数学者たち

GCD・LCMを含む整数論は、数学の中でもっとも古く、かつ現代最先端の分野の一つです。

ガウスは「数学は科学の女王、整数論は数学の女王」と述べ、整数論の中心性を強調しました。現代でも、ラングランズ・プログラム、abc予想（望月新一）、リーマン予想（未解決）など、最先端の研究テーマが数多く残されています。

よくある間違い・注意点

• 「GCD × LCM = 積」は2数のみ成立 — 2数の場合は必ず GCD(a,b)×LCM(a,b) = a×b が成立するが、3数以上では成立しない。例：GCD(4,6,8) = 2、LCM(4,6,8) = 24、2×24 = 48 ≠ 192。
• 試し割りで素因数分解を全数チェック — √n までの素数だけ試せば十分。n以下すべてを試すのは無駄。10⁹ でも約3万個の素数で完了。
• 「素数」と「互いに素」を混同 — 素数は1と自分自身以外に約数を持たない数。互いに素は「GCDが1」であること。9と16は互いに素だが、どちらも素数ではない。
• 1を素数と勘違い — 1は素数ではない（現代数学の定義）。素因数分解の一意性を保つため、素数は「1より大きい」と定義。歴史的には1を素数に含めた時代もあった。
• 0のGCD — GCD(a, 0) = |a|（数学的定義）。0はすべての整数の倍数と見なすため。負の数は絶対値で計算するのが慣例（GCD(−12, 18) = 6）。
• LCMがオーバーフロー — LCM = a×b÷GCD で先に掛け算するとオーバーフローの危険。a÷GCD×bの順に計算するのが定石。プログラミングでは特に重要。
• ユークリッド互除法の計算方向 — 「大きい数÷小さい数」の順で余りを求めて再帰。順序を逆にすると1ステップ増えるだけで結果は同じだが、教科書手順に従うのが無難。

参考文献・公的資料

整数論・GCD・LCM・素因数分解の学習内容および学術的基礎については、以下の公的機関・学術団体の資料を参照してください。

• 文部科学省 学習指導要領 ― 小学校算数・中学校数学・高等学校数学の学年別到達目標。約分・通分・素因数分解・ユークリッド互除法の学習範囲を規定。
• 日本数学会 ― 数学分野最大の学術団体。整数論・数論幾何の学術資料を発行。
• 日本数学教育学会 ― 数学教育の研究学会。分数指導・整数論教育の一次情報。
• 数学セミナー（日本評論社） ― 数学専門誌。整数論の入門〜研究レベルまで幅広く扱う。
• JMOOC（日本オープンオンライン教育推進協議会） ― 大学レベルの整数論・アルゴリズム講座を無料公開。
• IPA 情報処理推進機構 暗号技術ガイドライン ― RSA・ECCなど現代暗号の技術仕様。整数論の実応用の一次資料。
• OEIS（オンライン整数列大辞典） ― 素数・約数・完全数など整数列のデータベース。世界標準の参照リソース。
• Wolfram MathWorld: GCD/LCM ― 数学百科事典。公式・証明・アルゴリズムを網羅。
• American Mathematical Society (AMS) ― 米国数学会。整数論・暗号理論の学術リソース。
• AtCoder ― 日本最大の競技プログラミングコンテスト。ユークリッド互除法・拡張版の実装課題多数。

よくある質問（FAQ）

関連計算ツール