最大公约数/最小公倍数
最大公约数gcd是最大的能同时被a,b整除的正整数。最小公倍数lcm是最小的能同时整除a,b的正整数。即满足下列等式:
amodgcd=0bmodgcd=0lcmmoda=0lcmmodb=0 0和另一个正整数b的最大公约数为b,因为0除以任何正整数都可以整除。
对于a=36,能被a整除的正整数为divisorsa=[1,2,3,4,6,9,12,18,36],能整除a的正整数为multiplesa=[36,72,108…]。对于b=66,能被b整除的正整数为divisorsb=[1,2,3,6,11,22,33,66],能整除b的正整数为multiplesb=[66,132,198…]。那么36,66的最大公约数为6,最小公倍数为396。
将a=36,b=66分解为素数的乘积,可得36=2×2×3×3,66=2×3×11,其中每个素数都称为分解因子。可以把a和b的分解因子看作两个集合factora=[2,2,3,3],factorb=[2,3,11]。则a,b的最大公约数为两个正整数分解因子的最大交集,最小公倍数为最小并集
gcd(a,b)=factora⋂factorblcm(a,b)=factora⋃factorb 分解因子是一个NP完全问题。
最大公约数、最小公倍数具有以下性质:
gcd(a,b)×lcm(a,b)gcd(a,lcm(b,c))lcm(a,gcd(b,c))===a×blcm(gcd(a,b),gcd(a,c))gcd(lcm(a,b),lcm(a,c))