Fundamental Theorem of Arithmetic (Math Lair)

The Fundamental Theorem of Arithmetic states that every natural number greater than 1 can be factored into prime numbers 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:

m = p₁p₂p₃...p_r = q₁q₂q₃...q_s

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 p₁ = q₁. In this case, we would find that ^m/_p₁ has two different prime factorizations, namely p₂p₃...p_r and q₂q₃...q_s. However, this is impossible, because m was the smallest number with more than one factoring, and ^m/_p₁ 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 p₁ is not equal to q₁. Assume that p₁ 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:

n = (q₁ - p₁)q₂q₃...q_s = m - p₁q₂q₃...q_s

Obviously, n is smaller than m. In the first form, the factor (q₁ - p₁) may or may not be a prime, but p₁ will not be one of these factors. If p₁ were a factor of (q₁ - p₁), then p₁ would be a divisor of (q₁ - p₁). However, look at m - p₁q₂q₃...q_s. Both m and the other part both contain p₁ as a factor, so p₁ 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.