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

公開ツール約数・最大公約数・最小公倍数 計算機

目次
  1. 1. 約数の個数と素因数分解の公式
  2. 2. ユークリッドの互除法と最大公約数・最小公倍数の公式
  3. 約数・GCD・LCM計算機の使い方
  4. まとめ
  5. よくある質問

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)を求める):
    1. 120 ÷ 36 = 3 余り 12 → GCD(120, 36) = GCD(36, 12)
    2. 36 ÷ 12 = 3 余り 0 → 余りが0になったので、最後の割る数である 12 が最大公約数です。

最小公倍数の公式

最大公約数(GCD)がわかれば、最小公倍数(LCM)は次の式ですぐに求められます。

LCM(a, b) = (a × b) ÷ GCD(a, b)

約数・GCD・LCM計算機の使い方

桁数の大きい数の素因数分解や、ユークリッドの互除法の割り算を手で繰り返すのは大変です。そんなときは、整数論の計算に使える専用ツールを活用してみてください。

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

無料・登録不要。2つの数を入力すると、約数の一覧とGCD・LCMをすぐに計算します

使い方はとてもシンプルです。

  1. 数値を入力: 計算したい2つの自然数を、数値A・数値Bの入力欄にそれぞれ入力します(範囲は1〜1,000万)。
  2. 入力するとすぐに、詳細分析の欄に AとBそれぞれの約数の一覧、公約数の一覧、素因数分解の結果が表示されます。
  3. 同時に、上部の結果カードに 最大公約数(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 と一緒に再び計算機に入力すれば、数がいくつあっても順番に広げて求められます。


この記事は、ユークリッドの互除法をはじめとする整数論の標準的な数学理論を参考に、情報提供を目的として作成しました。

この記事は韓国語の原文をもとに作成しています。 韓国語の原文を読む

関連記事

  1. ロト6/45の1等確率と夢占い番号の選び方ロト6/45の1等確率が8,145,060分の1になる組合せの計算と、豚・火など夢の象徴ごとの韓国式の例示番号、「夢占いロト番号メーカー(韓国式)」の使い方を紹介します。
  2. ハンドドリップ 4:6メソッドの計算式とタイマー活用法ハンドドリップの基本となる抽出比(1:15)と、粕谷哲さんの4:6メソッドの仕組みを解説。段階ごとの注水量の出し方と、ブリューイングタイマーの使い方も紹介します。
  3. 出産予定日の計算方法|ネーゲレの法則と280日の数え方最終月経開始日から出産予定日を求めるネーゲレの法則と、妊娠週数の数え方を解説します。月経周期が28日と異なる場合の補正方法や、計算例もご紹介します。
  4. 定期預金・積立の中途解約利息の計算方法と担保貸付との比較預金・積立を中途解約したときの適用金利の計算式と、15.4%の利子所得税を差し引く仕組み、預金担保貸付と比べる際の考え方を解説します。
  5. エネルギー単位の換算|ジュール・カロリー・Wh・BTUジュール、カロリー、ワット時、BTUの定義と換算式を整理し、冷房能力や食品の熱量への当てはめ方、換算ツールの使い方まで解説します。
  6. 英文可読性の計算式|Flesch-Kincaidの求め方Flesch Reading EaseとFlesch-Kincaid Grade Levelの計算式を、単語数・文数・音節数の考え方とあわせて解説します。英文可読性レベル計算機の使い方も紹介します。

関連ツール