Vtyjkyuk

Let's say we're trying to find the Least Common Multiple of 36 and 18. First, we start off with the prime factorization of each number:

$$ 36 --> 2 * 2 * 3 * 3 $$
$$ 18 --> 2 * 3 * 3 $$

Next, we raise each factor to the highest number of times it appears in the factorization of each number and get the product to arrive at the LCM. In this case, that'd be: $ 2 * 2 * 3 * 3 $, since 2 appears twice in the factorization of 36 and 3 appears twice in the factorization of both 36 and 18.

My question is: we know this works; but why do we do what we do? What's an intuitive argument that can explain why this will get us to the LCM?

I would appeal to what happens when you say $a$ divides $b$. You can factor each into primes and you need the exponent on each prime in $b$ to be at least as large as the exponent on that prime in $a$. When we want both $a$ and $c$ to divide into $b$ we need the same thing for each, so the exponents in $b$ have to be the maximum of the exponents in $a$ and $c$.

I assume you and the person you are explaining this too accept the fundamental theorem of arithmetic - that a number can be written as a product of primes in just one way (order doesn't count).

Then show that if $c$ is a multiple of $a$ every prime factor of $a$ must appear at least as many times in the the factorization of $c$ as it does in $a$ - to see why just write

$$
c = a times text something
$$
and factor each side into primes
to see why.

Finally, what is the smallest $c$ that will work for both $a$ and $b$?

We will stick with natural numbers : that way you and I are more comfortable with notation.

The LCM of two natural numbers $a$ and $b$, is the smallest number $l$, such that there exist natural numbers $x,y$ such that $ax = by = l$. Very simple.

The concept of unique factorization helps see why one has this approach. Every natural number can be factored uniquely(up to order) into a product of primes.

Also, note that cancellation holds : if $n,x,y$ are natural numbers such that $nx = ny$, then $x = y$.

With this in mind, let us take two numbers $a$ and $b$. For simplicity, I will work out an example : the general case involves algebra which I do not want to wade into, since it would make the explanation more complicated.

Take $a = 24$ and $b = 126$. Now, write down the equation $ax = by = l$ :
$$
24 x = 126 y = l
$$

Prime factorize both sides :
$$
2 times 2 times 2 times 3 x = 2 times 3 times 3 times 7y
$$

Now, by unique factorization, both sides must prime factorize to the same set of primes. We conclude that $x$ must contain at least one $3$ and one $7$ in its factorization : this is exactly what the left hand side lacks in terms of primes to compensate the right hand side. Similarly, $y$ must contain at least two $2$s to compensate.

Consequently, $x = 21$ and $y = 4$ are the minimal choices for $x,y$ respectively.

Now, we are doing $24 times 21 = 504 = l$, or $126 times 4 = 504$ to get the answer.

But what really do $x,y$ capture? Well, they capture what I would call as "relative advantage" : imagine it is prestigious to have a higher power of a prime dividing you that another number. $x$ is capturing the relative advantage of $126$ over $24$ : the fact that $3^2$ and $7$ divide $126$. but only $3^1$ and $7^0 = 1$ divide $24$, gives $126$ an advantage over $24$. By how much? Well, by $3^2 - 1 times 7^1-0 = 21$.

When we multiply this $x$ by $24$, what are we doing? Well, we are giving $24$ an impetus : we are multiplying by the precise advantage of $126$ over $24$. The answer to this is $l$, by our earlier logic. But what is $l$ then? Well, let's put it this way : whatever prime has a higher power dividing $24$ more than $126$, in this case $2$, is already captured by $24$. However, $x$, captures the relative advantage of $126$ over $24$ ,so that $l$ contains the advantage of $126$ over $24$ as well in its prime factorization, namely $21 = 3 times 7$.

Now let's see what happened with each of the primes :

With $2$, we saw that $24$ contained more $2$s than $126$. So $x$ did not contain any $2$s, and hence the highest power of $2$ dividing $l$, is equal to the highest power of $2$ dividing $24$ , which is $2^3$.

With $3$, we saw that $126$ contains more $3$s than $24$. $24$ already has some number of $3$s though, but $x$ contains exactly those many number of threes, as the difference in the number of threes between $126$ and $24$, namely $1$. So the number $24x$, will contain the sum of these numbers, which is the number of times $3$ appears in $126$, equal to $2$. To put this in a better way, the advantage of $l$ is either the advantage of $24$, or the advantage of $24$, supplemented with the "relative advantage" of $126$ over $24$, which is the advantage of $126$.

A similar logic applies for $7$.

Consequently, we see where the maximum comes in in the prime factorization : the advantage of $24$, coupled with any "relative advantage" of $126$ over $24$ essentially captures (by coupled, I mean multipled since $l = 24 times x$), for a fixed prime, which one has a higher power of that prime as a factor.

Thus, the concept of "relative advantage" should be helpful to explain where the maximum comes in.