最小公倍數

能被整除所有指定的整數的最小正整數

最小公倍數(英語:least common multiple,lcm)是数论中的一个概念。若有一個數,可以被另外兩個數整除,且同時大於或等于,則公倍數的公倍數有無限個,而所有正的公倍數中,最小的公倍數就叫做最小公倍數。同样地,若干个整数公有的倍数中最小的正整数称为它们的最小公倍数。整数的最小公倍数一般记作:,或者参照英文记法记作

分數进行加減运算時,要求兩數的分母相同才能計算,故需要通分;标准的计算步骤是将兩個分數的分母通分成它们的最小公倍數,然后将通分后的分子相加。

与最大公因数之关系编辑

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

计算方法编辑

最小公倍数可以通过多种方法得到,最直接的方法是列举法,从小到大列举出其中一个数(如最大數)的倍数,当这个倍数也是另一个数的倍数时,就求得最小公倍数。另一个方法是利用公式 来求解,这时首先要知道它们的最大公因数。而最大公因数可以通过短除法得到。

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

其中 对应的最高次乘幂为 对应的最高次乘幂为 对应的最高次乘幂分别是 。将这些乘幂乘起来,就可以得到最小公倍数:

短除法

利用短除法,可以快速计算出多个整数的最小公倍数。

以下为例子:

假设我们要求12、20和42的最小公倍数。

a: 6 |12 18 42

b: 2 3 7

最小公倍数=a×b

因此,12、18和42和最小公倍数=6×2×3×7

所以,6×2×3×7=252,12、18和42的最小公倍数是252

递归计算多个整数的最小公倍数编辑

可以递归求出多个整数的最小公倍数:欲求 ,只需求

这利用了性质 。该性质证明如下:

的质因数分解分别为 ,其中 是第 个质数。

那么根据最小公倍数的定义,

证毕。

程式代碼编辑

以下使用輾轉相除法求得最大公因數,之後再求最小公倍數。

C#编辑

int GCD(int a, int b){return a % b == 0 ? b : GCD(b, a % b);}int LCM(int a, int b){return a * b / GCD(a, b);}

C编辑

int GCD(int a, int b) {if(b) while((a %= b) && (b %= a));return a + b;}int LCM(int a, int b) {return a * b / GCD(a, b);}

C++编辑

template<typename T>T GCD(T a, T b) {if (b) while((a %= b) && (b %= a));return a + b;}template<typename T>T LCM(T a, T b) {return a * b / GCD(a, b);}

Pascal编辑

function gcd(a,b:integer):longint;begin    if b=0 then gcd:=a    else gcd:=gcd(b,a mod b);end;function lcm(a,b:integer):longint;begin    lcm:=(a*b) div gcd(a,b);end;

Java编辑

int GCD(int a, int b) {return a % b == 0 ? b : GCD(b, a % b);}int LCM(int a, int b) { return a * b / GCD(a, b);}

Ruby编辑

def gcd(a, b)  b.zero? ? a : gcd(b, a % b)enddef lcm(a, b)  a * b / gcd(a, b)end

Python编辑

def gcd(a, b):    return a if b == 0 else gcd(b, a % b)    def lcm(a, b):    return a * b / gcd(a, b)

Go编辑

func GCD(a, b int) int {    if b == 0 {        return a    }return GCD(b, a%b)}func LCM(a, b int) int {return a * b / GCD(a, b)}

Swift编辑

func gcd(_ a: Int, _ b: Int) -> Int {    return b == 0 ? a : gcd(b, a % b)}func lcm(_ a: Int, _ b: Int) -> Int {    return a * b / gcd(a, b)}

應用编辑

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

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

參見编辑

參考來源编辑

  • 柯召,孙绮,孙琦. 《数论讲义》. 高等教育出版社. 2005. ISBN 753205473X. 
  • 阿尔伯特·H·贝勒著 谈祥柏译. 《数论妙趣:数学女王的盛情款待》. 上海教育出版社. 1998. ISBN 7040091909.