Least Common Multiple

Definition 1. Let $a, b \in \mathbb{Z}$, with $a \neq 0, b \neq 0$. The least common multiple of $a$ and $b$, denoted by lcm($a, b$), is $m \in \mathbb{N}$ satisfying the following:
(a) $a \,|\, m \wedge b \,|\, m$.
(b) $a \,|\, c \wedge b \,|\, c (c > 0) \Longrightarrow m \leq c$.

최대공약수와 마찬가지의 방법으로 lcm, 즉 최소공배수를 정의할 수 있다. 공배수이면서 ((a)) 공배수 중 가장 작은 수를 ((b)) 최소공배수라고 한다.

Theorem 1

Theorem 1. Let $a, b \in \mathbb{Z}$, with $a \neq 0, b \neq 0$. Then gcd($a, b$) lcm($a, b$) = $ab$.

Proof. Let gcd($a, b$) = $d$. Then $a = kd, b = ld$ for some $k, l \in \mathbb{Z}$. Then $\frac{ab}{d} = kb = la \Longrightarrow a \,|\, la = \frac{ab}{d} \wedge b \,|\, kb = \frac{ab}{d}$.
By Theorem 3, $d = ax + by$ for some $x, y \in \mathbb{Z}$. Suppose that $z = pa, z = qb (z > 0)$ for some $p, q \in \mathbb{Z}$. Then $d = ax + by = \frac{z}{p}x + \frac{z}{q}y \Longrightarrow dpq = zqx + zpy = z(qx + py) \Longrightarrow \frac{ab}{d} = \frac{z^2}{dpq} = \frac{z}{qx+py} \leq z$. Thus $\frac{ab}{d}$ = lcm($a, b$). $\blacksquare$