Divisibility and factorization · Definition

Least common multiple

elementary number theorydivisibility and factorization

Before you start you need to know

The least common multiple appears when adding fractions with different denominators and when synchronizing periodic events. It is computed from the greatest common divisor.

Definition

The least common multiple of two integers a and b is the smallest positive integer that is a multiple of both, denoted \( \operatorname{lcm}(a,b) \).

\[\operatorname{lcm}(a,b)=\dfrac{|ab|}{\gcd(a,b)}\]

If \( a \) and \( b \) are nonzero integers, \( \operatorname{lcm}(a,b) \) divides every common multiple of both, and \( \operatorname{lcm}(a,b)\cdot\gcd(a,b)=|ab| \) holds. Using prime factorization, \( \operatorname{lcm}(a,b) \) takes for each prime the largest exponent appearing in \( a \) or \( b \).

For \( a=12 \) and \( b=18 \), since \( 12=2^2\cdot 3 \) and \( 18=2\cdot 3^2 \), the least common multiple is \( 2^2\cdot 3^2=36 \). Check: \( \gcd(12,18)=6 \) and \( 12\cdot 18/6=36 \).

A typical mistake is multiplying \( a \) by \( b \) without dividing by the greatest common divisor, which gives \( 216 \) instead of \( 36 \). Another error is taking the smaller exponent of each prime instead of the larger one.

Think about it

Why is \( \operatorname{lcm}(a,b)=|ab| \) when \( \gcd(a,b)=1 \)?

Because \( \operatorname{lcm}(a,b)\cdot\gcd(a,b)=|ab| \), and with \( \gcd(a,b)=1 \) it gives \( \operatorname{lcm}(a,b)=|ab| \).

Exercises 10

  1. What is the least common multiple of \( 4 \) and \( 6 \)?
  2. What is the least common multiple of \( 5 \) and \( 7 \)?
  3. When adding \( \frac{1}{4} \) and \( \frac{1}{10} \), what is the smallest possible common denominator?
  4. If \( \gcd(a,b)=1 \), with \( a=14 \) and \( b=15 \), what is \( \operatorname{lcm}(a,b) \)?
  5. Two buses leave a stop, one every \( 8 \) minutes and the other every \( 14 \). After how many minutes do they depart together again?
  6. Compute \( \operatorname{lcm}(12, 20) \) using prime factorization.
  7. If \( \gcd(a,b)=4 \) and \( ab=96 \), what is \( \operatorname{lcm}(a,b) \)?
  8. What is the least common multiple of \( 8 \), \( 9 \) and \( 10 \)?
  9. Let \( a=2^3\cdot 3^2 \) and \( b=2\cdot 3\cdot 5^2 \). What is \( \operatorname{lcm}(a,b) \)?
  10. If \( \operatorname{lcm}(a,b)=180 \) and \( \gcd(a,b)=3 \), with \( a=45 \), what is \( b \)?

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 2
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 1