約数の個数とユークリッドの互除法|GCD・LCMの公式

1. 約数の個数と素因数分解の公式
大きな数のすべての約数を、1つずつ割って確かめるのは、計算量も時間もかかります。整数論では、素因数分解(Prime Factorization)を使った公式で、この手間を省くことができます。
約数の個数を求める公式: ある自然数 N が次のように素因数分解できるとき、
N = a^p × b^q × c^r × …(ここで a, b, c は互いに異なる素数、p, q, r は自然数の指数です。)
約数の総数 = (p + 1) × (q + 1) × (r + 1) × …計算例(72の約数の個数を求める):
- 素因数分解: 72 = 8 × 9 = 2^3 × 3^2
- 指数を当てはめる: p = 3, q = 2
- 約数の個数: (3 + 1) × (2 + 1) = 4 × 3 = 12個 結果の見方: 72の約数を指折り数えなくても、公式から全部で12個(
1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72)であることが確かめられます。
2. ユークリッドの互除法と最大公約数・最小公倍数の公式
2つの自然数の最大公約数を効率よく求める代表的なアルゴリズムが、紀元前300年ごろに確立されたユークリッドの互除法(Euclidean Algorithm)です。
ユークリッドの互除法の再帰式
2つの数 a と b (a > b)について、a を b で割った余りを r とすると、次の等式が成り立ちます。
GCD(a, b) = GCD(b, r)
この余りが0になったときの割る数が、2つの数の最大公約数です。
- 例(GCD(120, 36)を求める):
- 120 ÷ 36 = 3 余り 12 → GCD(120, 36) = GCD(36, 12)
- 36 ÷ 12 = 3 余り 0 → 余りが0になったので、最後の割る数である 12 が最大公約数です。
最小公倍数の公式
最大公約数(GCD)がわかれば、最小公倍数(LCM)は次の式ですぐに求められます。
LCM(a, b) = (a × b) ÷ GCD(a, b)
約数・GCD・LCM計算機の使い方
桁数の大きい数の素因数分解や、ユークリッドの互除法の割り算を手で繰り返すのは大変です。そんなときは、整数論の計算に使える専用ツールを活用してみてください。
無料・登録不要。2つの数を入力すると、約数の一覧とGCD・LCMをすぐに計算します

使い方はとてもシンプルです。
- 数値を入力: 計算したい2つの自然数を、数値A・数値Bの入力欄にそれぞれ入力します(範囲は1〜1,000万)。
- 入力するとすぐに、詳細分析の欄に AとBそれぞれの約数の一覧、公約数の一覧、素因数分解の結果が表示されます。
- 同時に、上部の結果カードに 最大公約数(GCD)と 最小公倍数(LCM)の値が太字で表示されます。素因数を使った計算の過程も、ステップごとに確認できます。
まとめ
約数、最大公約数、最小公倍数は基礎的な算数に見えますが、分数の四則演算、コンピューターの進数やビット演算、情報セキュリティにおける鍵の暗号化など、デジタルの世界を支える大切な考え方です。桁数が多い計算は手作業だとミスが混ざりやすいため、ユークリッドの互除法の結果を計算機で照らし合わせておくと、数値の誤りにすばやく気づけます。
無料・登録不要。2つの数を入力すると、約数の一覧とGCD・LCMをすぐに計算します
よくある質問
最大公約数が1になる2つの自然数は何と呼ばれ、なぜ重要なのですか?
最大公約数が1だけである2つの数の関係を、数学では互いに素(Relatively Prime / Coprime)と呼びます。
- 互いに素であることは、分数をこれ以上約分できない既約分数にするときの重要な基準になります。
- 特にコンピューターの暗号技術(RSA)では、大きな素数を2つ選んでその積(n)を求め、n から導いた値と互いに素な整数を公開鍵の生成に使います。このように、互いに素かどうかの判定は、暗号鍵を作る過程の基本的な前提になっています。
3つ以上の数(例: A, B, C)の最大公約数と最小公倍数はどうやって求めますか?
この計算機は一度に2つの数を入力する方式なので、3つ以上の場合は2つずつ順番に入力して、結果をつなげて求めます。
最大公約数の拡張公式:
GCD(A, B, C) = GCD(GCD(A, B), C)(つまり、まず A と B を計算機に入力して最大公約数を求め、その結果と C をもう一度計算機に入力すると、3つの数すべての最大公約数が求められます。)
最小公倍数の拡張公式:
LCM(A, B, C) = LCM(LCM(A, B), C)同じように、まず A と B の最小公倍数を求め、その値を C と一緒に再び計算機に入力すれば、数がいくつあっても順番に広げて求められます。
この記事は、ユークリッドの互除法をはじめとする整数論の標準的な数学理論を参考に、情報提供を目的として作成しました。
この記事は韓国語の原文をもとに作成しています。 韓国語の原文を読む