GCD · LCM を素因数分解とベン図で視覚化
整数 A と B を入力すると
GCD と LCM が自動で計算されます
ユークリッドの互除法でGCDを求め、GCDからLCMを算出します。
GCD: a = b × q + r を繰り返し、r = 0 になったときの b が GCD
LCM(a, b) = a × b ÷ GCD(a, b)
例えば、84と120のGCDを求める場合、120 = 84×1 + 36、84 = 36×2 + 12、36 = 12×3 + 0 となり、GCD = 12です。LCM = 84×120÷12 = 840 となります。素因数分解では、GCDは共通因数の最小指数の積、LCMは全因数の最大指数の積です。
Q. GCDとLCMはどんな場面で使いますか？
A. GCD（最大公約数）は分数の約分、タイルの敷き詰め問題、暗号化（RSA暗号）などで使われます。LCM（最小公倍数）は分数の通分、周期的なイベントの同期（歯車の回転、バスの時刻表など）で活用されます。
Q. 3つ以上の数のGCD・LCMはどう求めますか？
A. 3つ以上の数の場合は、2つずつ順に求めます。例えばGCD(a, b, c) = GCD(GCD(a, b), c)です。LCMも同様にLCM(a, b, c) = LCM(LCM(a, b), c)として計算できます。
ユークリッドの互除法は紀元前300年頃にユークリッドの「原論」に記載された、現存する最古のアルゴリズムの一つです。非常に効率的で、大きな数に対しても高速に動作するため、現代のコンピュータサイエンスでも広く使われています。
数論においてGCDは重要な概念で、2つの整数のGCDが1のとき「互いに素」といいます。RSA暗号など現代の暗号技術は、大きな素数のGCDに関する計算の困難さを安全性の基盤としています。