因數倍數

重點

\(ab = \gcd(a, b) \times lcm(a, b)\)

定理1

對於整數 \(a, b\) 我們稱 \(a, b\) 的最大公因數，是最大的正整數 \(d\) 使得 \(d \mid a\) 且 \(d \mid b\)，記作 \(d = \gcd(a, b)\)。當 \(\gcd(a, b) = 1\) 時，我們稱 \(a, b\) 互質。

定理2

\(\gcd(a, b) \neq 1 \iff \exists p \text{ 是質數使得 } p \mid a \text{ 且 } p \mid b\)
(如果兩個數字 \(a\) 和 \(b\) 的最大公因數 \(\gcd(a, b)\) 不等於 1，這意味著存在一個質數 \(p\) 使得 \(p\) 同時整除 \(a\) 和 \(b\)。)

定理3

\(lcm(a, b)\) 被定義為最小的正整數 \(L\) 使得 \(a \mid L\) 且 \(b \mid L\)。

定理4

若 \(a = p_1^{k_1} p_2^{k_2} \dots p_m^{k_m}\)，\(b = p_1^{t_1} p_2^{t_2} \dots p_m^{t_m}\)，則：

\[
\gcd(a, b) = p_1^{\min(k_1, t_1)} p_2^{\min(k_2, t_2)} \dots p_m^{\min(k_m, t_m)}
\]

\[ 
lcm(a, b) = p_1^{\max(k_1, t_1)} p_2^{\max(k_2, t_2)} \dots p_m^{\max(k_m, t_m)}
\]

有了定理 3、4，我們就能夠將 \(\gcd\) 與 \(lcm\) 連結在一起了：

定理5

\(ab = \gcd(a, b) \times lcm(a, b)\)