Definition

A least common multiple (LCM) is $m \in \mathbf{Z_{\geq 0}}$ such that:

$a \ | \ m$ and $b \ | \ m$
If $n \in \mathbf{Z}$, $a \ | \ n$ and $b \ | \ n$, then $m \ | \ n$.

In fact the LCM is unique if it exists. To prove it’s existence we’ll need the following definition

Definition (Well Ordering Principle)

A non-empty subset of $\mathbf{N}$ has a smallest element

Next, we’ll prove the existence of the LCM.

Proposition

The LCM always exists

Proof
Let $a, b \in \mathbf{Z}$. Let $J = \mathbf{Z}a \cap \mathbf{Z}b$. We want to show that $J$ itself is a set of multiples so we can write $J = \mathbf{Z}m$ for some $m \in \mathbf{Z}_{\geq 0}$. This means that $m$ must be the LCM of $a$ and $b$ by definition. [Why? If $J = \mathbf{Z}m$, then $m$ is the least element in $J$, all the other elements are multiples of $m$. We have $a \ | \ m$ and $b \ | \ m$ because $J$ also contains common multiples of $a$ and $b$. And for any $n \in \mathbf{Z}$, if $a \ | \ n$ and $b \ | \ n$, then $m \ | \ n$. This is true because $m$ is the smallest of all these common multiples.] We will use division by remainder to prove this!

Observe that $J$ is closed under addition and subtraction. So if $c, d \in J$, then any integer combination of $c$ and $d$ will be in $J$. So for any $m, n \in \mathbf{Z}$, $cm + dn \in J$.

We have two cases:
Case 1: If either $a = 0$ or $b = 0$, then $J = \{0\} = \mathbf{Z}0$.

Case 2: If $a \neq 0$ and $b \neq 0$, then $J$ is the set of common multiples of $\mathbf{Z}a$ and $\mathbf{Z}b$. Consider $J \cap \mathbf{N}$. This is the set of positive common multiples. This set is not empty because it will at least include $|ab|$. So $J \cap \mathbf{N}$ is a non-empty subset of $\mathbf{N}$. By the well-ordering principle, there is a smallest number in $J \cap \mathbf{N}$. Let $m \in J \cap \mathbf{N}$ be the smallest common multiple. (so we’re setting $m$ to be the smallest positive common multiple of $\mathbf{Z}a$ and $\mathbf{Z}b$)

We claim that $J = \mathbf{Z}m$ (the set of multiples of $m$). We will show this by proving that $J \subseteq \mathbf{Z}m$ and that $\mathbf{Z}m \subseteq J$.

$\mathbf{Z}m \subseteq J$: This is true since $m \in J$ and we showed earlier that $m$ is closed under addition and subtraction so any multiple of $m$ is also in $J$ and therefore $\mathbf{Z}m \subseteq J$.

$J \subseteq \mathbf{Z}m$: Suppose $x \in J = \mathbf{Z}a \cap \mathbf{Z}b$. Consider what happens when we divide $x$ by $m$. We can write $x = qm + r$. with $q, r \in \mathbf{Z}$ and $0 \leq r < m$. Re-write the equation as

$$ \begin{align*} r = x - qm. \end{align*} $$

Observe now that $x \in J$ by assumption. $qm$ is a multiple of $m$ so it’s in $J$. So their difference is also in $J$ which means that $r \in J$. If $r = 0$, $x = qm \in \mathbf{Z}m$ and we’re done. If $r \neq 0$, then $r \in J$, then $r \in J \cap \mathbf{N}$ but also $r < m$. But that’s a contradiction because $m$ is the smallest element in $J \cap \mathbf{N}$ and so this case doesn’t happen. So $J = \mathbf{Z}m$ as desired. $\ \blacksquare$.

Consequences of the LCM

The next few propositions are some consequences of the LCM.

Proposition

If $d = gcd(a,b) = 1$, then $m = lcm(a,b) = ab$

Proof
We are given that $d = gcd(a,b) = 1$. This means that $a$ and $b$ are relatively prime. Condition 1 is true since $a \ | \ ab$ and $b \ | \ ab$. For condition two of the LCM definition, let $n \in \mathbf{Z}$ such that $a \ | \ n$ and $b \ | \ n$. By the proposition from lecture 5, $ab \ | \ n$. (Proposition: If $a$ and $b$ are relatively prime, then if $a \ | \ n$ and $b \ | \ n$, then $ab \ | \ n$). $\ \blacksquare$

Proposition

Let $e$ be a common divisor of $a$ and $b$ so $e \ | \ a$ and $e \ | \ b$. Then $lcm(\frac{a}{e}, \frac{b}{e}) = \frac{1}{e} lcm(a,b)$.

Proof
[TODO] $x$ is a common divisor of $\frac{a}{e}$ and $\frac{b}{e}$ if and only if $xe$ is a common divisor of $a$ and $b$.

Proposition

If $a, b \in \mathbf{N}$, $d = gcd(a,b)$ and $m = lcm(a,b)$, then $m = \frac{ab}{d}$

Proof
We need the previous two propositions

If $d = 1$, then $m = lcm(a,b) = ab$
If $e \ | \ a$ and $e \ | \ b$, then $lcm(\frac{a}{e}, \frac{b}{e}) = \frac{1}{e} lcm(a,b)$

If we divide both $a$ and $b$ by $d$, their gcd will become 1 so $gcd(\frac{a}{d}, \frac{b}{d}) = 1$. Since the gcd is 1, then $lcm(\frac{a}{d}, \frac{b}{d}) = \frac{b}{d}\frac{a}{d}$ by part $(1)$. So now let $e = d$, so by $(2)$,

$$ \begin{align*} \frac{1}{d} lcm(a, b) &= lcm(\frac{a}{d}, \frac{b}{d}) \\ \frac{m}{d} &= \frac{b}{d}\frac{a}{d} \\ m &= \frac{ab}{d} \\ \end{align*} $$

Pairwise Relatively Prime

Definition

$a_1,...,a_k \in \mathbf{Z}$ are pairwise relatively prime if $gcd(a_i,a_j) = 1$ for all $1 \leq i,j \leq k, i \neq j$

Some facts based this:

Lemma

If $a_1,...,a_k \in \mathbf{Z}$ are pairwise relatively prime, then $a_k,b = a_1,...,a_{k-1}$ are relatively prime so $gcd(a_k,b) = 1$.

Proof
Suppose for the sake of contradiction that $a_k$ and $b$ are not relatively prime so they have a common divisor. Let $p$ be a prime that is a common divisor of $a_k$ and $b$. So $p \ | \ b$ which means that $p \ | \ a_1a_2...a_{k-1}$. But since $p$ is prime, then by the proposition from the previous lecture, $p$ must divide one of the factors in $a_1a_2...a_{k-1}$. Let $p$ divide $a_i$ for some $1 \leq i \leq k - 1$. However $p \ | \ p_k$. This means that $gcd(a_i,a_k) \neq 1$. This is a contradiction since we assumed that $a_1,...,a_k$ are pairwise relatively prime. Therefore, we must have $a_k$ and $b$ be relatively prime. $\ \blacksquare$

The consequence of this lemma is the following

Proposition

If $a_1, a_2,...,a_k$ are pairwise relatively prime and if $a_i \ | \ n$ for all $i = 1,...,k$, then $a_1a_2,...,a_k \ | \ n$

Proof
By Induction on $k$
Base Case: If $k=1$, then there is nothing to prove.
If $k = 2$, then $gcd(a_1,a_2)=1$. If $a_1 \ | \ n$ and $a_1 \ | \ n$, then by the proposition from lecture 5, we must have $ab \ | \ n$.

Inductive Case $k \geq 3$:
Let $b = a_1a_2...a_{k-1}$. By the previous lemma we know that $gcd(a_k,b) = 1$. Also by the inductive hypothesis if $a_1,...,a_{k-1} \ | \ n$, then $a_1...a_{k-1} = b \ | \ n$. but $gcd(a_k,b) = 1$ so $a_k$ and $b$ are relatively prime. Since they are relatively prime and they both divide $n$, then $ba_k = a_1...a_{k-1}a_k$ also divides $n$ as we wanted to show. $\ \blacksquare$

References

MATH417 by Charles Rezk
Algebra: Abstract and Concrete by Frederick M. Goodman