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.
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.
