最細公倍數

最細公倍數（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$ 係最細公倍數。