[1] Proof by induction that if a positive integer has a prime factorization, then it is unique.
We're inducting over Z_N, where Z_N is the set of all positive integers with at least one known prime factorization using exactly N number of primes. Call this factorization Pn = p_1 * p_2 * ... p_n
For every case, split into proof by cases and contradiction: suppose there is an element Z in set Z_N had another factorization Fn.
- If Fn has the same number of factors as Pn, divide both sides by p_i. Since Fn / p_i must be an integer, Fn must contain p_i, or else one of its factors f_i actually isn't prime by Euclid's Lemma.
- If Fn has k more factors than Pn, then divide Pn by (f_1 * f_2 * ... * f_n). Then (f_n+1 * ... * f_n+k) = X for some composite integer X > 1. Thus Fn = X * (f_1 * f_2 * ... * f_n) = (p_1 * p_2 * ... * p_n) = Pn. Since (p_1 * p_2 * ... * p_n)/Z must be an integer, Z must divide into one of the factors p_i by Euclid's lemma, which is impossible since they are prime by definition.
- Similar argument to above if Pn has more factors.
[2] Proof by contradiction: Every positive integer Y greater than one has a prime factorization.
Suppose not. We know Y = Y * 1. So Y must be composite in order for it to not have a prime factorization. Hence, we know that Y = a * b, (a, b > 1). At least one of the two must be composite or else Y has a prime factorization, so let's say (a) is composite. Then a = c * d (c, d > 1). Then at least one of the two factors must be non prime or else we've found the prime factorization for Y. Repeat ad infinitum to show that if Y does not have a prime factorization, then it must be the product of an infinite number of composite factors, with every factor great than 1. Hence contradiction.
So every positive integer greater than 1 has a prime factorization, and it must be unique.