The proof by contradiction and proof by induction are very similar.
Proof by Contradiction
Any integer greater than 1 can be factored into primes in one and only one way.
Because…
We can show this factoring happens in at least one way, and we then show it happens in only one way.
Part One: Existence
Any integer greater than 1 can be factored into primes.
Because…
If some integer x greater than 1 can't be factored into primes then we get a contradiction.
Because…
If the smallest integer x0 greater than 1 can't be factored into primes then we get a contradiction.
Because…
The integer x0 is either prime or it's not.
If it's prime then it has itself as a prime factor. This contradicts our assumption that x0 is the smallest integer with no prime factors.
If it's not prime then it can be factored into primes. This contradicts our assumption that x0 is the smallest integer with no prime factors.
Because…
If the integer x0 is not prime then it has factors that can be factored into primes.
Because…
If the integer x0 is not prime then it has a smaller factor.
That factor times another factor will equal x0.
Both factors can be factored into primes.
Because…
Both these factors are less than x0, which was the smallest number that we claimed couldn't be factored into primes.
Part Two: Uniqueness
This factoring is unique: there's only one possible way to factor an integer greater than 1.
Because…
If you assume there is more than one way you'll get a contradiction.
Because…
If there are two different factorings then you'll end up with a contradiction.
Because…
There is only one list of prime factors.
Because…
You can pair each prime in one list with the identical prime in the other list, with no leftovers.
Because…
A product divided by a prime factor loses that instance of the prime from both lists until there are no more primes in each list.
Because…
A prime factor never divides another prime factor.
Proof by Induction
Any integer greater than 1 can be factored into primes in one and only one way.
Because…
We can show this factoring happens in at least one way, and we then show it happens in only one way.
Part One: Existence
Any integer greater than 1 can be factored into primes.
Because…
We can prove this by induction (base step and induction step).
Because…
The smallest integer greater than 1 can be factored into primes (base step).
And if all integers up to N can be factored into primes, then so can N (induction step).
Because…
The integer 2 can be factored as a product of primes: 2 = 2. That proves the base step.
And if all integers up to N can be factored into primes, then so can N. That proves the induction step.
Because…
N can be factored into primes.
Because…
All of N's factors can be factored into primes.
Because…
All of N's factors are smaller than N. By assumption integers smaller than N can be factored into primes.
Part Two: Uniqueness
This factoring is unique: there's only one possible way to factor an integer greater than 1.
Because…
This factoring is unique for our base step and our induction step.
Because…
We know 2 = 2. There is no other way to factor 2.
Also, our induction step is true.
Because…
If 2 had more than one factor then it wouldn't be prime.
Also, our induction step is true.
Because…
Assume there are two products of primes. Then those two products are identical.
Because…
Take any factor from one list. Divide it into both products. The two new products are identical.
Because…
If a factor divides one list it divides the other list, eliminating that instance of the factor from both lists.
The smaller products are identical.
Because…
A prime divides only a prime, so a prime eliminates only itself from both lists.
The list of factors now multiplies out to a product less than N. This product is unique.
Because…
By our assumption for the induction step, all integers greater than 1 but less than N can be factored in one and only one way.
Older Material
Here are rewrites of the proofs I did previously. As far as I know they're accurate, just wordy.
Integers and their prime factors
Also called the Unique Factorization Theorem[2], the Fundamental Theorem of Arithmetic says that any integer greater than 1 may be factored into primes, and in only one way.
Proof by contradiction
In this proof from [1] we prove things in three steps: any integer greater than 1 has a prime divisor, any integer greater than 1 is the product of primes, and this product of primes is unique.
Proof
Any integer greater than 1 is the product of one and only one set of prime factors.
Why?
Because we can show that any integer x greater than 1 has at least one prime factor, implying x equals at least one product of primes, and this product is unique.
Why does x have at least one prime factor?
Because if we assume x doesn't have such a prime factor we get a contradiction.
Why?
We can choose x such that it's the smallest integer greater than 1 that doesn't have a prime factor. If x is prime then it has a prime factor (itself). If x isn't prime then it has factors less than itself. But any integer less than x (by assumption) will have prime factors. So x has factors that in turn have prime factors. So x has prime factors.
Why is x the product of primes?
Assume x is the smallest integer greater than 1 that doesn't equal a product of primes. Then we get a contradiction.
Why?
Either x is prime or not prime. If x is prime it equals a product of primes (just itself). If x is not prime we know from our earlier result that x will have at least one prime factor. That prime factor multiplied by some integer will equal x. But that integer is less than x so it will equal a product of primes. Therefore all the factors of x will equal products of primes. So x will equal a product of primes.
Why is this product of primes unique?
If we imagine two different products of primes both equalling x then we get a contradiction.
Why?
We find that any prime that divides into one product will divide into the other. But primes divide into primes only if they're equal. So one by one we divide out identical primes from both products, until they're all paired.
Why?
Since both products of primes equal x, if prime p is a factor in one product it will divide into the other product of primes. This means it will divide into one of its terms. But the only way a prime divides into a prime is if the primes are equal. So you can divide both products by that prime to make two equal, smaller products. Repeat the process until all primes are paired. Because a prime in one product can always be paired with a prime in the other, we conclude there'll be no terms in one product left over at the end. Therefore the two products will have identical factors.
Proof by induction
In [2] this result is called the Unique Factorization Theorem for Integers. Induction is used to prove the existence of a prime factorization and its uniqueness. While [1] treats separately the existence of a prime factor and the existence of a product of such factors, [2] uses induction in a way that merges those two issues.1
Proof
Any integer greater than 1 can be factored into a product of prime numbers, and uniquely so.
Why?
We can use induction to show that for any x this product of prime numbers exists, and that it's unique.
Why does it exist?
Since x is any integer greater than 1, we set our base step to x = 2. Clearly 2 = 2, and since 2 is prime, we've shown 2 is a product of primes.
For our induction step we assume x is a product of primes for any x less than N. If N is prime then it's a product of primes. If N is not prime then its factors are all less than N. But we've already assumed all x less than N are products of primes. Therefore all of N's factors are products of primes. Therefore N is a product of primes.
Why is this product of primes unique for each x?
We can show through induction that all products of primes equalling an arbitrary x are identical.
Why?
Our base step will be a product of one prime. A product of one prime equals just that prime. And it can't equal a product of more than one term otherwise it wouldn't be prime. So we've proved for any product of one prime that it's unique.
Now for our induction step assume all products with less than r primes are unique. Consider the product of r prime terms. Let it equal x. Imagine another product of primes that also equals x. Then any prime that divides one product will divide, and therefore equal, some prime in the other product.
Divide out this prime from both products. Now we're comparing a product of r–1 prime terms with another product. Since our induction assumption holds for r–1 terms, we know both of these products are identical. The factor we had divided was identical on both sides, so both products having r primes will be identical, and hence unique.
With our base step and our induction step proved, we've proved our hypothesis for all r greater than 1.
Advisory
Please note that I am not a mathematician and so the presentation of proofs that I make may be deeply flawed. I'm using this writing process to figure out what I'm reading. Please consult more authoritative sources as well.
Feel free to contact me by leaving a comment or sending me a private message.
