Letβs use induction on the size of So our base case is which is of course prime so it has (the) unique factorization
For the induction step, first suppose we have proved that all numbers up to can be written as a product of primes (uniquely or not). Then we look at to continue the induction.
By induction, this shows that a prime factorization exists for all numbers up to It remains to be shown that such a factorization is unique.
So first rewrite our factorization in a given order (such as nondecreasing):
Now letβs look at another possible representation, possibly with different primes:
At this point we need
Corollary 6.3.7. By assumption,
divides
Hence, by the corollary,
divides at least one of the
But the only positive divisors of a prime are itself and 1, and
is prime (not one), so
Cancel these from both products to get two different representations of (the integer) as a product of primes. By the induction hypothesis, since this number is less than these representations are unique up to reordering, so multiplying both by to get must also be unique up to reordering.
By induction, we are done.