Why does the LCM long division method work?

Question

We're all familiar with the popular 'long division method' for finding the LCM of two numbers.

For example, to find the LCM of 36 and 24, we do something like this:

2 |24, 36 (divide both numbers by a common prime factor, and write the quotient below)
2 |12, 18
3 |6, 9

• |2, 3 (stop dividing at this point, as there is no common factor)
  

Now, the LCM is (2 x 2 x 3) x (2 x 3) = 72, obtained by multiplying the factors on the left column, with the uncommon factors which remain in the last row.

This somehow appears to be black magic. I've searched quite a few websites, as well as some books. None of them actually mention why this method works. I've tried figuring it out on my own too, but with no success.

Answer 1

What you are doing in your scheme is exactly factoring out the common prime factors $p_1,...,p_n$ from your two numbers $a,b$ (the numbers on the left side of your scheme). What is left after this factoring process are numbers $A$ and $B$ that do not share any more common primes to factor out (the bottom numbers of your scheme). We have

$$(*)\qquad a=p_1\cdots p_n\cdot A,\qquad b=p_1\cdots p_n\cdot B.$$

Now, note

$$\mathrm{lcm}(a,b)=a\cdot B=b\cdot A$$

because $B$ is exactly the factor missing from $a$ to make it a multiple of $b$ (you see $a\cdot B$ contains the primes $p_i$ and the factor $B$, exactly what $b$ needs). Equivalently for $A$ and $b$. So choose one of these identities $-$ say $a\cdot B$ $-$ and plug in $a$ from $(*)$ to get

$$\mathrm{lcm}(a,b)=a\cdot B=p_1\cdots p_n\cdot A\cdot B,$$

and this is exactly what you learned. The $p_i$ are from the left and the $A$ and $B$ are the numbers from the bottom.

Answer 2

I'll try and give a very elementary answer (with no use of prime numbers), but I'll use bigger numbers to make the argument clearer. ($2$ and $3$ are too simple in your example.)

Say you have the numbers $132$ and $156$, and you want to find their LCM. The first thing you do is you divide out by common factors until you get to $11$ and $13$, which have no common factors. You've divided by $12$.

Now write down the multiples of $132$ and $156$ as follows: $$132, 264, 396, \dots$$ $$156, 312, 468, \dots$$

You are looking for the first time the same number appears in both lists. Obviously, this will happen in exactly the same position in each list if you make all the numbers in the lists $12$ times smaller, as follows: $$11, 22, 33, \dots$$ $$13, 26, 39, \dots$$

Now I'm going to ask you to accept temporarily that when two numbers have no common factors, then their lcm is equal to their product. So the first number that is common to both of the smaller lists is $11 \times 13$. Now it's clear that the first number common to the larger lists much be $12$ times this, or $12 \times 11 \times 13$. So that explains the method.

Proof that $\operatorname{lcm}(a,b) = ab$ when $\gcd(a,b) = 1$.

An important fact, which I'll prove below, is that given any two numbers $a$ and $b$, any common multiple of the two numbers is a multiple of their least common multiple. If we accept this fact, then the claim above can be proved as follows.

Let $M$ be the lcm of $a$ and $b$. So $\frac{M}{a}$ and $\frac{M}{b}$ are whole numbers. Since $ab$ is also a common multiple of $a$ and $b$, it must be a multiple of $M$. Thus $\frac{ab}{M} = d$ is a whole number. Now $a = \frac{M}{b} d$, so $a$ is a multiple of $d$. Similarly, $b$ is a multiple of $d$. By hypothesis then, $d = 1$, so $M = ab$, which is what we wanted.

Proof that all common multiples of $a, b$ are multiples of $M = \operatorname{lcm}(a,b)$.

If N is a common multiple of $a$ and $b$, divide $N$ by $M$ to get $$N = qM + r, \quad 0 \leq r < M,$$ where $q$ and $r$ are the quotient and the remainder of the division.

Now $qM$ is a common multiple of $a$ and $b$, as is $N$, so the remainder $r = N - qM$ must be a common multiple as well. Since $M$ is assumed to be the smallest positive common multiple of $a$ and $b$, we must have $r = 0$. This proves that $N$ is a multiple of $M$, as we wanted.