gcd和lcm的相关性质

acm中经常涉及到最大公约数gcd和最小公倍数的关系。

先说一个定理：任何一个正整数n都可以进行素因子分解成：
n = p1 ^e1 * p2^e2 * … * pr^er; （其中pr是<= n 的素数因子）

两个整数a=10,b=24 他们的最大公约数为gcd, 最小公倍数为lcm 则有
a,b都能分解为有限个素数的积 10 = 2¹ *3⁰ * 5¹ , 24 = 2³ *3¹ * 5⁰

性质1：lcm(a,b)=a*b/gcd(a,b)

性质2：gcd(a,b) 为a,b公共素因子取最小指数的积gcd = 2¹ = 2

性质3：lcm(a,b) 为a,b所有素因子取最大指数的积lcm = 2³ * 3¹ * 5¹ = 120

以上性质可以推至多个数,但是性质1求最大公约数时需要稍作改变，是利用前两个数的lcm和第三个数的乘积:
lcm(a1, a2, a3)=lcm(lcm(a1,a2),a3)
gcd(a1, a2, a3)=gcd(gcd(a1,a2),a3)