Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

2.4: Least Common Multiple

( \newcommand{\kernel}{\mathrm{null}\,}\)

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 a,b.

2,8=8,

5,8=40

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

a=pa11pa22...panm

and

b=pb11pb22...pbnm,

where (as above) we exclude any prime with 0 power in both a and b. Then a,b=pmax(a1,b1)1pmax(a2,b2)2...pmax(an,bn)m, 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 ab. Then

max(a,b)=aand  min(a,b)=b, and the result follows.

Note

Let a and b be two positive integers. Then

  1. a,b0;
  2. a,b=ab/(a,b);
  3. If am and bm, then a,bm

Proof

The proof of part 1 follows from the definition.

As for part 2, let

a=pa11pa22...panmand  b=pb11pb22...pbnm.

Notice that since

(a,b)=pmin(a1,b2)1pmin(a2,b2)2...pmin(an,bn)n

and

a,b=pmax(a1,b1)1pmax(a2,b2)2...pmax(an,bn)m, then a,b(a,b)=pmax(a1,b1)1pmax(a2,b2)2...pmax(an,bn)mpmin(a1,b2)1pmin(a2,b2)2...pmin(an,bn)n=pmax(a1,b1)+min(a1,b1)1pmax(a2,b2)+min(a2,b2)2...pmax(an,bn)+min(an,bn)m=pa1+b11pa2+b22...p(an+bn)n=pa11pa22...panmpb11pb22...pbnm=ab

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)m (Exercise 6). Thus a,bm.

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 25567211 and 23587213.
  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)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.


This page titled 2.4: Least Common Multiple is shared under a CC BY license and was authored, remixed, and/or curated by Wissam Raji.

Support Center

How can we help?