The fundamental theorem of arithmetic (FTA), also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than either is prime itself or is the product of a unique combination of prime numbers.
For every integer , it can be expressed as a product of prime numbers:
The following proof shows that every integer greater than is prime itself or is the product of prime numbers. It is adapted from the Strong Induction wiki:
Base case: This is clearly true for .
Inductive step: Suppose the statement is true for .
If is prime, then we are done. Otherwise, has a smallest prime factor, which we denote by . Let . Since , by our inductive hypothesis, can be written as the product of prime numbers. That means can also be written as a product of primes. We're done!
The following proof shows that there is only one way to express an integer with the product of an unordered set of primes.
The proof uses Euclid's lemma: If a prime divides the product of two positive integers and , then divides or divides (or both).
Assume that integer is the product of prime numbers in two different ways: For simplicity, we let the arrangements of prime be in ascending order.
By Euclid's lemma, since are coprime integers (in fact, they are all primes), can and must divide only one of the primes. Note that is the smallest prime, then we have . By the same method, we reach that all and thus . Then we conclude that the combination of primes are the same.
Given the polynomial with integer coefficients and given that there exist four distinct integers and such that show that there is no integer for which .
Let . Then we must have for some . Let be such that , Then and we get By the fundamental theorem of arithmetic, we can express 3 as a product of at most three different integers . Since, and are all distinct, this is an obvious contradiction.