calculate 最大公約数・最小公倍数計算ツール star

最大公約数(GCD)と最小公倍数(LCM)はどう計算する?

2つの数の最大公約数(GCD)とは、両方をあまりなく割り切る最大の数のことです。これを求める最も速い方法が、紀元前300年頃から知られているユークリッドの互除法です。大きい方の数を小さい方の数で割り、大きい方の数を割り算の余りに置き換えて同じ操作を繰り返します。最終的に余りが0になったとき、その直前の0でない余りがGCDです。

具体例 — GCD(48, 18): 48 = 2 × 18 + 12、次に18 = 1 × 12 + 6、次に12 = 2 × 6 + 0。余りがちょうど0になったので、その時点の除数である6がGCDです。素因数分解は一切不要で、わずか3ステップで終わりました — この速さこそ、電卓やコンピュータが内部で試し割りではなくユークリッドの互除法を使う理由です。

最小公倍数(LCM)は、元の2つの数がどちらも割り切れる最小の数です。GCDが分かれば、LCMはただ1つの式から直接求まります: LCM(a,b) = (a × b) ÷ GCD(a,b)。同じ数の組で計算すると、LCM(48,18) = (48 × 18) ÷ 6 = 864 ÷ 6 = 144となります。GCD × LCM = a × bという関係は任意の2つの正の整数について常に成り立ち、手計算した答えを手早く検算する便利な方法にもなります。

3つ以上の数の場合、このツールはリストを2つずつ順番に処理します。まずGCD(a,b)を求め、次にその結果とcのGCDを求め、以下同様に続けます。LCMも同じ方法で、1つずつ数を取り込みながら計算します。

知っておくべきこと

• 分数の約分。分数を最も簡単な形に約分するには、分子と分母をそれぞれのGCDで割ります。24/36はGCD(24,36) = 12なので、一度の計算で2/3に約分できます — 試行錯誤は不要です。
• 通分。分母の異なる分数を足すとき、分母同士のLCMを使えば最小の共通分母が得られ、分母を単純に掛け合わせるよりも扱いやすい数のまま計算できます。
• 互いに素な数。2つの数が1以外に共通の因数を持たない場合(例:8と9)、GCDは1になり、LCMは単純にその積になります — GCD(8,9) = 1、LCM(8,9) = 72。
• よくある間違いは、3つ以上の数のGCDをそのうちの2つだけから求めてしまうことです。2つの数に共通する因数がすべての数に共通するとは限らないため、必ずリスト全体を対象に計算してください。
• 実生活での使い道。LCMは「2つの繰り返しスケジュールが再び重なるのはいつか」という問いに答えます(12分おきと18分おきに出発する2台のバスは、LCM(12,18) = 36分ごとに同時に発車します)。一方GCDは「同じ大きさの最大グループにいくつ分けられるか」という問いに答えます。