与最大公因数之关系

两个整数的最小公倍数与最大公因数之间有如下的关系：

计算方法

最小公倍数可以通过多种方法得到，最直接的方法是列举法，从小到大列举出其中一个数（如最大数）的倍数，当这个倍数也是另一个数的倍数时，就求得最小公倍数。另一个方法是利用公式 lcm ⁡ ⁡ --> ( a 1 , a 2 ) = a 1 a 2 gcd ( a 1 , a 2 ) {\displaystyle \operatorname {lcm} (a_{1},a_{2})={\frac {a_{1}a_{2}}{\gcd(a_{1},a_{2})}}} 来求解，这时首先要知道它们的最大公因数。而最大公因数可以通过短除法得到。

利用整数的唯一分解定理，还可以用质因数分解法。将每个整数进行质因数分解。对每个质数，在质因数分解的表达式中寻找次数最高的乘幂，最后将所有这些质数乘幂相乘就可以得到最小公倍数。譬如求216、384和210的最小公倍数。对216、384和210来说：

程式代码

以下使用辗转相除法求得最大公因数，之后再求最小公倍数。

C#

privateintGCD(inta,intb){if(b)while((a%=b)&&(b%=a));returna+b;}privateintLCM(inta,intb){returna*b/GCD(a,b);}

C

intGCD(inta,intb){if(b)while((a%=b)&&(b%=a));returna+b;}intLCM(inta,intb){returna*b/GCD(a,b);}

C++

templateTGCD(Ta,Tb){if(b)while((a%=b)&&(b%=a));returna+b;}templateTLCM(Ta,Tb){returna*b/GCD(a,b);}

PASCAL

1、vara,b,ans:integer;functiongcd(a,b:integer):longint;beginifb=0thengcd:=aelsegcd:=gcd(b,amodb);end;2、vara,b,ans:integer;functionlcm(a,b:integer):longint;beginreadln(a,b);ans:=(a*b)divgcd(a,b);write(ans);end;

JAVA

privateintGCD(inta,intb){returna%b==0?b:GCD(b,a%b);}privateintLCM(inta,intb){returna*b/GCD(a,b);}

应用

求最小公倍数是进行分数加减法时的步骤之一。将分母通分时，会把所有分数的分母通分为它们的最小公倍数，然后将分子相加。例如：

其中分母42就是21与6的最小公倍数。

参见

公倍数

公因数

最大公因数

参考来源

柯召，孙绮，孙琦. 《数论讲义》. 高等教育出版社. 2005. ISBN 753205473X. 

阿尔伯特﹒H﹒贝勒著 谈祥柏译. 《数论妙趣：数学女王的盛情款待》. 上海教育出版社. 1998. ISBN 7040091909. 

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。