Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic states that every natural number greater than 1 can be factored into primes in exactly one way (the order of the factors doesn't matter). For example, the only way that 4 can be factored into primes is as 2 × 2. This is an important result in number theory.
Start by assuming the opposite of what we want to prove; i.e., assume that there is at least one natural number with two distinct factors. The set of such numbers must contain a smallest element; call it m. Since m is the smallest natural number with this property, every natural number smaller than m has the unique factorization property, while m itself has at least two different factorizations. We can express these factorizations as:
Where all of the p's and q's represent some prime number or another.
To start the proof, we'll show that each of the p's must be entirely different from each of the q's. For example, if the prime 5 appears in the first batch, it can't appear in the second batch. If the two batches did have a common prime, we could arrange the notation so that the common prime would be the first one in the batch, thus p1 = q1. In this case, we would find that m/p1 has two different prime factorizations, namely p2p3...pr and q2q3...qs. However, this is impossible, because m was the smallest number with more than one factoring, and m/p1 is smaller than m.
We have shown that all of the p's are different from all of the q's. In particular, we know that p1 is not equal to q1. Assume that p1 is the smaller of the two. We can assume this because the notation is symmetric between the two batches of primes. If this weren't the case we could just interchange the p's and q's and get the same result anyway.
Now look at:
Obviously, n is smaller than m. In the first form, the factor (q1 - p1) may or may not be a prime, but p1 will not be one of these factors. If p1 were a factor of (q1 - p1), then p1 would be a divisor of (q1 - p1). However, look at m - p1q2q3...qs. Both m and the other part both contain p1 as a factor, so p1 is a factor of the entire expression. Therefore, n has two different prime factorizations. However, since n is smaller than m, this contradicts our deduction that m was the smallest number with more than one prime factorization. Therefore, our assumption must be false, and all natural numbers have only one prime factorization.
Last updated June 16, 2001. URL: http://www.stormloader.com/ajy/ftoa.html For questions or comments email James Yolkowski. Math Lair home page