最小公倍數

最小公倍數是数论中的一个概念。若有一個數${\displaystyle X}$，可以被另外兩個數${\displaystyle A}$、${\displaystyle B}$整除，且${\displaystyle X}$大於（或等于）${\displaystyle A}$和${\displaystyle B}$，則${\displaystyle X}$為${\displaystyle A}$和${\displaystyle B}$的公倍數。${\displaystyle A}$和${\displaystyle B}$的公倍數有無限個，而所有正的公倍數中，最小的公倍數就叫做最小公倍數。同样地，若干个整数公有的倍数中最小的正整数称为它们的最小公倍数。${\displaystyle n}$整数${\displaystyle a_{1},a_{2},\cdots ,a_{n}}$的最小公倍数一般记作：${\displaystyle [a_{1},a_{2},\cdots ,a_{n}]}$，或者参照英文记法记作${\displaystyle \operatorname {lcm} (a_{1},a_{2},\cdots ,a_{n})}$，其中lcm是英语中“最小公倍数”一词（least common multiple）的首字母缩写。

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

与最大公因数之关系

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

${\displaystyle \operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}}$ 

计算方法

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

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

${\displaystyle 216=2^{3}\times 3^{3}}$ ，${\displaystyle 384=2^{7}\times 3^{1}}$ ，${\displaystyle 210=2^{1}\times 3^{1}\times 5^{1}\times 7^{1}}$ 。

其中${\displaystyle 2}$ 对应的最高次乘幂为${\displaystyle 2^{7}}$ ；${\displaystyle 3}$ 对应的最高次乘幂为${\displaystyle 3^{3}}$ ；${\displaystyle 5}$ 和${\displaystyle 7}$ 对应的最高次乘幂分别是${\displaystyle 5^{1}}$ 与${\displaystyle 7^{1}}$ 。将这些乘幂乘起来，就可以得到最小公倍数：

${\displaystyle [216,384,210]=2^{7}\times 3^{3}\times 5^{1}\times 7^{1}=120960}$ 。

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

可以递归求出多个整数的最小公倍数：欲求 ${\displaystyle \operatorname {lcm} (a_{1},...,a_{n})(n\geq 3)}$ ，只需求 ${\displaystyle \operatorname {lcm} (a_{1},...,a_{n-2},\operatorname {lcm} (a_{n-1},a_{n}))}$ 。

这利用了性质 ${\displaystyle \operatorname {lcm} (a_{1},a_{2},a_{3})=\operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2}),a_{3})}$ 。该性质证明如下：

记 ${\displaystyle a_{1},a_{2},a_{3}}$  的质因数分解分别为${\displaystyle \prod _{i=1}^{n}p_{i}^{e_{1i}},\prod _{i=1}^{n}p_{i}^{e_{2i}},\prod _{i=1}^{n}p_{i}^{e_{3i}}}$ ，其中 ${\displaystyle p_{i}}$  是第 ${\displaystyle i}$  个质数。

那么根据最小公倍数的定义，${\displaystyle \operatorname {lcm} (a_{1},a_{2},a_{3})=\prod _{i=1}^{n}p_{i}^{\max(e_{1i},e_{2i},e_{3i})}}$ ，

${\displaystyle \operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2}),a_{3})=\operatorname {lcm} (\prod _{i=1}^{n}p_{i}^{\max(e_{1i},e_{2i})},a_{3})=\prod _{i=1}^{n}p_{i}^{\max(\max(e_{1i},e_{2i}),e_{3i})}=\prod _{i=1}^{n}p_{i}^{\max(e_{1i},e_{2i},e_{3i})}}$ ，

证毕。

程式代碼

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

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) end def 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) 

Golang

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) } 

应用

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

${\displaystyle {2 \over 21}+{1 \over 6}={4 \over 42}+{7 \over 42}={11 \over 42}}$ 

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

参见

• 公倍数
• 公因数
• 最大公因数

参考来源

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