GCD 和 LCM 的關係？

對任意正整數 a,b：GCD(a,b)×LCM(a,b)=a×b。先求 GCD（歐幾里得演算法），再除得 LCM，比直接列舉更快。

歐幾里得演算法怎麼算 GCD？

反覆用「大數 mod 小數」替換：GCD(48,18)=GCD(18,12)=GCD(12,6)=GCD(6,0)=6，直到餘數為 0，最後的除數即 GCD。

gcd(a,b) · lcm(a,b) = |a·b|

Compute the greatest common divisor and least common multiple of a set of integers.

📐 計算公式

gcd(a,b)·lcm(a,b) = |a·b|

輾轉相除法求最大公約數，再求最小公倍數。

整數 a

整數 b

📌 計算說明

約分與通分

GCD(12,18)=6，故 12/18 約分為 2/3；LCM(4,6)=12，故 1/4 與 1/6 通分分母為 12。關係：LCM(a,b)=a×b/GCD(a,b)，即 4×6/2=12。

互質判斷

GCD(8,15)=1，兩數互質；互質時 LCM=兩數之積。

GCD 和 LCM 的關係？: 對任意正整數 a,b：GCD(a,b)×LCM(a,b)=a×b。先求 GCD（歐幾里得演算法），再除得 LCM，比直接列舉更快。
歐幾里得演算法怎麼算 GCD？: 反覆用「大數 mod 小數」替換：GCD(48,18)=GCD(18,12)=GCD(12,6)=GCD(6,0)=6，直到餘數為 0，最後的除數即 GCD。

最大公約數(GCD)為兩整數公有最大因子；最小公倍數(LCM)為最小公共倍數。滿足 GCD(a,b)·LCM(a,b)=|a·b|。

約分、通分、週期對齊、模運算等。常用歐幾里得演算法（輾轉相除）高效求解。