Monday Math: The Uniqueness of Prime Factorizations

The big number theory class has moved on to prime factorizations and the fundamental theorem of arithmetic. As it happens, though, I've already done a post on that subject.

Looking back at what I wrote then I see that I left out one important detail. I asserted without proof (though I did provide a link) that if a prime divides the product of two other numbers then it had to divide one of the two factors already. The proof of that result requires something that we estblished last week. So let's have a look.

Last week we mentioned that it is a consequence of the Euclidean algorithm that if a and b are integers with

then we can find (possibly negative) integers x and y such that

In particular, if a and b are relatively prime then we can find x and y so that

Very nice. But how is that helpful?

Now let p be a prime number. We want to show:

To accomplish that we shall assume that p does not divide a, and show that this implies that p does divide b.

Well then. If p does not divide a then we must have that

If that is not clear then remember that the only divisors of a prime number are one and the number itself. But since we are assuming that p does not divide a, we know that p cannot be the greatest common divisor in this case. That leaves one as the only possibility.

Since p and a are relatively prime, we can apply our little trick to find x and y so that

Multiplying both sides by b produces

Look carefully at the left-hand side. I claim that we have:

The first of those is obvious. The second follows immediately from our assumption that p divides ab. But those two together imply that p divides the left-hand side. It follows that p divides the right-hand side as well, which is exactly what we were trying to show.

Done and done.