Skip to main content

Section 8.6 LCM and GCD via prime factorizations

Definition 8.6.1.

The least common multiple \(\lcm(a,b)\) of positive integers \(a\) and \(b\) is the smallest positive integer divisible by both \(a\) and \(b\text{.}\)

For example, \(\lcm(15,12)=60\text{.}\)

We leave the proof of this as an exercise.

If \(a=120=2^3\cdot 3\cdot 5\) and \(b=36=2^2\cdot 3^2\text{,}\) then \(\gcd=2^2\cdot 3=12\) and \(\lcm=2^3\cdot 3^2 \cdot 5=360=\frac{120\cdot 36}{12}\text{,}\)

Since \(r\) is rational, there are integers \(a'\) and \(b'\) such that \(r = \frac{a'}{b'}\text{,}\) with \(b' \neq 0\text{.}\) Without loss of generality, we may assume that \(b'>0\text{.}\) If we find \(-r = \frac{a}{b}\) with \(a\) and \(b\) coprime, then \(r = \frac{-a}{b}\) with \(-a\) and \(b\) coprime, so we may assume that \(r\geq 0\text{.}\)

Now let \(p_1, \cdots, p_k\) be the prime numbers that divide either \(a'\) or \(b'\text{.}\) We may therefore write

\begin{equation*} a' = p_1^{m_1}\cdots p_k^{m_k} \ \ \text{ and } b' = q_1^{n_1}\cdots q_k^{n_k}\text{,} \end{equation*}

where each exponent \(m_i\) and \(n_i\) is nonnegative. Now for each \(i\text{,}\) let

\begin{equation*} s_i = \max(m_i-n_i, 0)\ \ \text{ and } t_i = \max(n_i-m_i, 0)\text{.} \end{equation*}

Thus for each \(i\text{,}\) at most one of \(s_i\) and \(t_i\) is nonzero, and

\begin{equation*} \frac{p_i^{m_i}}{q_i^{n_i}} = \frac{p_i^{s_i}}{q_i^{t_i}}\text{.} \end{equation*}

Thus we set

\begin{equation*} a = p_1^{s_1}\cdots p_r^{s_k} \ \ \text{ and } b = q_1^{t_1}\cdots q_k^{t_k}\text{,} \end{equation*}

and we find that

\begin{equation*} r = \frac{a'}{b'} = \frac{a}{b}\text{.} \end{equation*}

Now

\begin{equation*} \gcd(a,b) = p_1^{\min(s_1,t_1)}\cdots p_r^{\min(s_k,t_k)} = p_1^0\cdots p_r^0 = 1. \qedhere \end{equation*}

Now let us prove that \(a\) and \(b\) are unique with this property. If \(c\) and \(d\) are coprime integers with \(d \geq 1\text{,}\) and if \(r = \frac{c}{d}\text{,}\) then \(ad = bc\text{.}\) Since \(a\) and \(b\) are coprime, it follows that \(b\) divides \(d\text{,}\) and since \(c\) and \(d\) are coprime, it follows that \(d\) divides \(b\text{.}\) Thus \(d=b\text{,}\) and so \(a=c\) as well.