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

ユークリッドアルゴリズムで最大公約数（GCD）と最小公倍数（LCM）を段階的に計算します。

最大公約数・最小公倍数計算機とは？

最大公約数（GCD）と最小公倍数（LCM）は、初等整数論において最も重要な概念の2つであり、中学校での分数の簡略化からインターネットを守る暗号アルゴリズムまで幅広い応用があります。

紀元前300年頃にユークリッドによって記述されたユークリッドの互除法は、数学で最も古く且つ最も効率的なアルゴリズムの1つです。O(log(min(a,b)))ステップでGCDを計算し、非常に大きな数でも高速に終了します。このアルゴリズムは、GCD(a, b) = GCD(b, a mod b)という恒等式を剰余がゼロになるまで繰り返し適用します。

この計算機は、2つの数に対する完全なユークリッドの互除法をステップごとに表示し、一般化 GCD(a, b, c) = GCD(GCD(a, b), c) を使用して複数の数のリストに対するGCDとLCMも計算します。

計算式

ユークリッドの互除法：

GCD(a, b) = GCD(b, a mod b) b = 0まで

GCDからLCMを求める：

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)

計算方法

2つの正の整数aとbを入力します。
整数の除算を適用：a = q×b + r。
aをbで、bをrで置き換えます。r = 0になるまで繰り返します。
最後の非ゼロの剰余がGCDです。
基本恒等式を使用してLCM = |a × b| / GCDを計算します。
3つ以上の数には「複数の数」モードを使用します。

例

GCD(48, 18)を求める：48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0。GCD = 6。LCM = |48×18|/6 = 864/6 = 144。確認：144/48 = 3 ✓、144/18 = 8 ✓。

重要な用語の説明

GCD：両方の数を余りなく割り切る最大の整数
LCM：両方の数で割り切れる最小の正の整数
互いに素：GCD = 1の2つの数、共通の素因数を持たない
ユークリッドの互除法：繰り返し除算によりGCDを計算する古代のアルゴリズム
剰余演算：a mod bはaをbで割った余り
整除性：b/aに余りがない場合、aはbを割り切る

よくある使用例

分数の簡略化：a/bをGCD(a, b)で両方割って約分する
異なる分母の分数の足し算：分母のLCMを求める
スケジューリング：2つの繰り返しイベントが次に同時に発生する時期を求める
RSA鍵生成：指数eがφ(n)と互いに素であることを確認する
機械工学における歯車比の問題
タイルパターンデザイン：最小の繰り返し単位を見つける

よくある質問

GCD（最大公約数）とは何ですか？どのように計算しますか？

GCD（最大公約数）は、aとbの両方を余りなく割り切る最大の正の整数です。ユークリッドの互除法は効率的に計算します：(a, b)をb = 0になるまで繰り返し(b, a mod b)に置き換えます。最後の非ゼロの値がGCDです。

LCM（最小公倍数）とは何ですか？何に使われますか？

LCM（最小公倍数）は、aとbの両方で割り切れる最小の正の整数です。異なる分母の分数の足し算、スケジューリング問題、音楽理論で使用されます。

GCDとLCMの関係は？

GCD(a, b) × LCM(a, b) = |a × b| です。GCDがわかれば、LCMは単に |a × b| / GCD(a, b) です。これは倍数を列挙するより効率的です。

「互いに素」とはどういう意味ですか？

2つの数が互いに素（相対的に素数）であるとは、それらのGCDが1であることを意味します。つまり、共通の素因数を共有しません。互いに素であることは、モジュラー算術、暗号理論、中国剰余定理の基礎です。

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