State the fundamental theorem of Arithmetic.
It says that any whole number greater than 1 is either prime itself or can be expressed as a product of two or more primes.
e.g.
600 = 2x2x3x5
247 = 13x19
the factors in both examples are all made up of primes
The Fundamental Theorem of Arithmetic states that every positive integer greater than 1 can be expressed as a unique product of prime numbers, up to the order of the factors.
To understand and prove this theorem, we can follow these steps:
1. Start with the statement that every positive integer greater than 1 can be expressed as a product of primes. We assume this is true and want to prove that the expression is unique.
2. Assume there are two different prime factorizations for the same integer, such as n = p₁ * p₂ * p₃ and n = q₁ * q₂ * q₃.
3. Since p₁ is a prime factor of n, it must also be a factor of q₁ * q₂ * q₃. Using the fundamental property of primes, p₁ must divide at least one of the q's. Without loss of generality, assume p₁ divides q₁.
4. Now, q₁ = p₁ * k for some positive integer k. We substitute this into the second expression, giving us n = p₁ * p₂ * p₃ and n = (p₁ * k) * q₂ * q₃.
5. By canceling out p₁ from both sides, we have p₂ * p₃ = k * q₂ * q₃.
6. We repeat the same process for p₂, resulting in it dividing one of the q's. Without loss of generality, assume p₂ divides q₂.
7. By canceling out p₂ from both sides, we get p₃ = k * q₃.
8. Continuing this process, we eventually conclude that every prime factor of n must divide one of the corresponding q's.
9. However, this leads to a contradiction because we initially assumed that n has two different prime factorizations.
10. Hence, our assumption that two different prime factorizations exist is false, demonstrating that the expression for n as a product of primes is unique.
In summary, the Fundamental Theorem of Arithmetic guarantees that every positive integer greater than 1 can be expressed as a unique product of prime numbers, confirming the existence of prime factorization.