最細公倍數

最細公倍數（Least Common Multiple，簡寫L.C.M.），又叫最小公倍數，係兩個或以上嘅整數入面嘅最細嗰個倍數。譬如12同10嘅最細公倍數就係60。數學會用$lcm(a,b)$嚟表示a同b呢兩個數字嘅最細公倍數。

定義

假設有兩個整數$a,b\in \mathbb {Z}$。最細公倍數$m\in \mathbb {Z} _{>0}$係一個正整數符合以下條件：

• $a|m$同埋$b|m$。
• 如果有另一個整數$c\in \mathbb {Z} _{>0}$係符合$a|c$同埋$b|c$，咁$m$必須符合$m\leq c$。

最細公倍數公式

求兩個整數$a,b\in \mathbb {Z}$嘅最細公倍數，可以利用以下公式：

$$lcm(a,b)={\frac {a\times b}{gcd(a,b)}}$$

證明：

假設$d=gcd(a,b)$。根據GCD嘅定義，$a=md$同埋$b=dn$，$m,n\in \mathbb {Z}$係某啲整數。

將上面兩條式乘埋，得出

$${\begin{aligned}ab&=(md)(dn)\\mnd&={\frac {ab}{d}}\\\end{aligned}}$$

而家將$l={\frac {ab}{d}}$，咁$l=an=bm$。即係$l$又係$a$嘅倍數，又係$b$嘅倍數，咁$l$就係一個公倍數。

假設$l'$係$a$同$b$是但一個公倍數。咁樣$l'=af=bg$，$f$同$g$係某啲整數。

同時$a$同$b$都有GCD，咁就可以用比舒公式，得出$d=ax+by$，$x$同$y$係某啲整數。

而家要計算$l'$除$l$，如果除得盡嘅話，$l$就係最細公倍數。

$${\begin{aligned}{\frac {l'}{l}}&={\frac {l'}{\frac {ab}{d}}}\\&={\frac {l'd}{ab}}\\&={\frac {l'(ax+by)}{ab}}\\&={\frac {l'ax}{ab}}+{\frac {l'by}{ab}}\\&={\frac {l'}{b}}x+{\frac {l'}{a}}y\\\end{aligned}}$$

因為$l'$係其中一個公倍數，所以一定可以被$a$同$b$除得盡。

$${\begin{aligned}{\frac {l'}{l}}&=gx+fy\end{aligned}}$$

因此$l|l'$，所以$l\leq l'$。所以$l$係最細公倍數。

例子

如果要搵12345同246810既LCM。

利用輾轉相除法，得知$gcd(12345,246810)=1$。

所以，$lcm(13579,246810)={\frac {13579\times 246810}{1}}=3351432990$。

推論

假設有兩個整數$a,b\in \mathbb {Z}$，佢哋係相對質數，咁佢哋嘅最細公倍數就係$lcm(a,b)=a\times b$。

證明：

利用最細公倍數公式得知，$lcm(a,b)={\frac {a\times b}{gcd(a,b)}}$。

因為$a$同$b$嘅GCD係1，所以$lcm(a,b)={\frac {a\times b}{1}}=a\times b$。

睇埋

• 最大公因數