2.4: Least Common Multiple

We can use prime factorization to find the smallest common multiple of two positive integers.

The least common multiple (l.c.m.) of two positive integers is the smallest positive integer that is a multiple of both.

We denote the least common multiple of two positive integers \(a\) an \(b\) by \(\langle a,b\rangle\).

\(\langle2,8\rangle=8\),

\(\langle5,8\rangle=40\)

We can figure out \(\langle a,b\rangle\) once we have the prime factorization of \(a\) and \(b\). To do that, let

\[a=p_1^{a_1}p_2^{a_2}...p_m^{a_n}\]

and

\[b=p_1^{b_1}p_2^{b_2}...p_m^{b_n},\]

where (as above) we exclude any prime with 0 power in both \(a\) and \(b\). Then \(\langle a,b\rangle=p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}...p_m^{\max(a_n,b_n)}\), where \(\max(a,b)\) is the maximum of the two integers \(a\) and \(b\). We now prove a theorem that relates the least common multiple of two positive integers to their greatest common divisor. In some books, this theorem is adopted as the definition of the least common multiple. To prove the theorem we present a lemma

If a and b are two real numbers, then

\[\min(a,b)+\max(a,b)=a+b\]

Assume without loss of generality that \(a\geq b\). Then

\[\max(a,b)=a \hspace{0.2cm}\mbox{and} \ \ \min(a,b)=b,\] and the result follows.

Note

Let \(a\) and \(b\) be two positive integers. Then

1. \(\langle a,b\rangle\geq 0\);
2. \(\langle a,b \rangle=ab/(a,b)\);
3. If \(a\mid m\) and \(b \mid m\), then \(\langle a,b \rangle \mid m\)

Proof

The proof of part 1 follows from the definition.

As for part 2, let

\[a=p_1^{a_1}p_2^{a_2}...p_m^{a_n} \mbox{and} \ \ b=p_1^{b_1}p_2^{b_2}...p_m^{b_n}.\]

Notice that since

\[(a,b)=p_1^{\min(a_1,b_2)}p_2^{\min(a_2,b_2)}...p_n^{\min(a_n,b_n)}\]

and

\[\langle a,b\rangle=p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}...p_m^{\max(a_n,b_n)},\] then \[\begin{aligned} \langle a,b \rangle(a,b)&=&p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}...p_m^{\max(a_n,b_n)} p_1^{\min(a_1,b_2)}p_2^{min(a_2,b_2)}...p_n^{\min(a_n,b_n)}\\ &=& p_1^{\max(a_1,b_1)+\min(a_1,b_1)}p_2^{\max(a_2,b_2)+\min(a_2,b_2)}...p_m^{\max(a_n,b_n)+\min(a_n,b_n)}\\&=& p_1^{a_1+b_1}p_2^{a_2+b_2}...p_n^{(a_n+b_n)}\\&=&p_1^{a_1}p_2^{a_2}...p_m^{a_n}p_1^{b_1}p_2^{b_2}...p_m^{b_n}=ab\end{aligned}\]

Note also that we used Lemma 8 in the above equations. For part 3, it would be a nice exercise to show that \(ab/(a,b) \mid m\) (Exercise 6). Thus \(\langle a,b \rangle \mid m\).

\(\square\)

Exercises

1. Find the least common multiple of 14 and 15.
2. Find the least common multiple of 240 and 610.
3. Find the least common multiple and the greatest common divisor of \(2^55^67^211\) and \(2^35^87^213\).
4. Show that every common multiple of two positive integers \(a\) and \(b\) is divisible by the least common multiple of \(a\) and \(b\).
5. Show that if \(a\) and \(b\) are positive integers then the greatest common divisor of \(a\) and \(b\) divides their least common multiple. When are the least common multiple and the greatest common divisor equal to each other.
6. Show that \(ab/(a,b) \mid m\) where \(m=<a,b>\).

Contributors and Attributions

• Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.