Least Common Multiple

We define the LCM and state some properties tying the concepts of GCD and LCM to the Fundamental Theorem of Arithmetic.

Definition (Least Common Multiple) The least common multiple of two nonzero integers and is the smallest positive integer that is divisible by and

Example (Least Common Multiple) The least common multiple of and 21 is The least common multiple of and 36 is The least common multiple of 2 and 20 is The least common multiple of 7 and 11 is

One immediate result from the Fundamental Theorem of Arithmetic is the ability to find the GCD and LCM from a factorization of two given integers. Say we are given and and we are able to find the unique factorization of each (and assume that all exponents are nonnegative and the are all primes in both and ), namely

then

because for each prime in and have exactly factors of in common.

Proposition (Least Common Multiple and Greatest Common Divisor) If and are positive integers, then

    Proof. Let and have prime factorization; namely


Now we can form the set of primes consists of all the and So we can write

where the exponents are zero where necessary. Now let and Then, we have,

Example (Least Common Multiple) Show that if and are integers, then if and only if and

Solution. Suppose Since and it follows that and Conversely, suppose and Using the unique factorization theorem we can write and Then for and because and Hence,

Example (Least Common Multiple and Greatest Common Divisor) Show that if and are positive integers, then

Solution. Let be a prime that divides or Then divides and Hence divides both sides of the equation Define, and by and say and Without loss of generality, suppose Then so Also, But so Therefore, But so the same power of divides both sides of the equation. Therefore, the two sides must be equal.

Cite this as:
Least Common Multiple
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/least-common-multiple.html