睇最細公倍數嘅原碼

'''最細公倍數'''（Lowest Common Multiple，簡寫'''L.C.M.'''），又叫'''最小公倍數'''，係兩個或以上嘅[[整數]]入面嘅最細嗰個[[倍數]]。譬如[[12]]同[[10]]嘅最大公因數係[[60]]。數學會用<math>lcm(a,b)</math>嚟表示a同b呢兩個數字嘅最細公倍數。

== 定義 ==
假設有兩個整數<math>a,b\in\Z</math>。最細公倍數<math>m\in\Z_{>0}</math>係一個正整數符合以下條件：
* <math>a|m</math>同埋<math>b|m</math>。
* 如果有另一個整數<math>c\in\Z_{>0}</math>係符合<math>a|c</math>同埋<math>b|c</math>，咁<math>m</math>必須符合<math>m\leq c</math>。

== 最細公倍數公式 ==
求兩個整數<math>a,b\in\Z</math>嘅最細公倍數，可以利用以下公式：
<math display="block">lcm(a,b)=\frac{a\times b}{gcd(a,b)}</math>

'''證明：'''

假設<math>d=gcd(a,b)</math>。根據[[最大公因數|GCD]]嘅定義，<math>a=md</math>同埋<math>b=dn</math>，<math>m,n\in\Z</math>係某啲整數。

將上面兩條式乘埋，得出<math display="block">\begin{align}
ab &= (md)(dn)\\
mnd&=\frac{ab}{d}\\
\end{align}</math>而家將<math>l=\frac{ab}{d}</math>，咁<math>l=an=bm</math>。即係<math>l</math>又係<math>a</math>嘅倍數，又係<math>b</math>嘅倍數，咁<math>l</math>就係一個公倍數。

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

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

而家要計算<math>l'</math>除<math>l</math>，如果除得盡嘅話，<math>l</math>就係[[最細公倍數]]。<math display="block">\begin{align}
\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{align}</math>因為<math>l'</math>係其中一個公倍數，所以一定可以被<math>a</math>同<math>b</math>除得盡。<math display="block">\begin{align}
\frac{l'}{l} &= gx+fy

\end{align}</math>因此<math>l|l'</math>，所以<math>l\leq l'</math>。所以<math>l</math>係最細公倍數。

== 例子 ==
如果要搵12345同246810既LCM。

利用輾轉相除法，得知<math>gcd(12345,246810)=1</math>。

所以，<math>lcm(13579,246810)=\frac{13579\times246810}{1}=3351432990</math>。

== 推論 ==
假設有兩個整數<math>a,b\in\Z</math>，佢哋係相對質數，咁佢哋嘅最細公倍數就係<math>lcm(a,b)=a\times b</math>。

'''證明：'''

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

因為<math>a</math>同<math>b</math>嘅[[GCD]]係1，所以<math>lcm(a,b)=\frac{a\times b}{1}=a\times b</math>。

==睇埋==
*[[最大公因數]]


{{數學基礎課題}}
{{數論}}
[[Category:數論]]
[[Category:算術]]
[[Category:數學]]