I read it a couple days ago and actually remembered it this time in a way that I will never forget it. It invokes Euclid’s lemma, which states that if for prime, then or , which can be proved using Bezout’s lemma. For existence, it does induction on the number of factors, with as the trivial base case. For the non base case, wherein our number is composite, apply the inductive hypothesis on the factors. For uniqueness, assume two distinct factorizations: . By Euclid’s lemma, each of the s divides and is thus equal to one of the s. Keep invoking Euclid’s lemma, canceling out a prime factor on each iteration and eventually we must end with in order for the two sides to be equal.

### Like this:

Like Loading...