Wednesday, March 25, 2020

Prime factorization

I was re-reading Hardy's classic A Mathematician's Apology and was reminded of the proof of the Fundamental Theorem of Arithmetic that I found in his book (with Wright) An Introduction to the Theory of Numbers (to be honest:  reading the whole thing has been beyond me so far).

I just love this proof, so I wrote it up (pdf).  I believe every step is clearly explained.  If not, let me know.

One thing that's great about this theorem is it leads to a very easy proof that the square root of 2 is not rational.

Theorem:  there do not exist integers a and b such that a^2 = 2 b^2.

Proof.  By contradiction.

- a and b each have unique prime factorizations.  a and b do not share any factors, for if they did, we should be able to cancel those factors.

- a^2 contains two copies of each of the factors of a, and similarly for b^2.  So the count of the prime factors of a^2 is even and the same is true for b^2.

- But then, since 2 is prime, there is an odd number of prime factors on the right-hand side above, and an even number on the left-hand side.   Since every prime factorization is unique, this is impossible.

The proof is easily extended to the general case where we suppose that a^2 = p b^2.

In fact, it turns out that the only true cases occur for $a^2 = c b^2$, where $c$ is a perfect square, with duplicated factors, and b^2 is equal to 1, so that a = c.