Fundamental Theorem of Arithmetic
Every natural number can be written uniquely (up to ordering) as a product of primes.
Proof
Induction on proves existence, exactly as in the proposition above. For uniqueness, induct on . The statement is true for . Let and suppose the statement holds for all natural numbers . Suppose
where all are primes. Then divides , so by Euclid’s lemma divides for some ; since is prime, , and without loss of generality . Cancelling from both sides leaves
a natural number less than . By the inductive hypothesis and, after reordering, for all . Hence and for all after reordering.
Failure in other arithmetic systems
There are “arithmetic systems” permitting and in which factorisation is not unique. Consider , the set of all numbers of the form where , with addition and multiplication defined as usual. In this system one can define what it means to be a “prime”, and happen to be primes in this sense. Yet , so factorisation is not unique: uniqueness of prime factorisation genuinely relies on the arithmetic of the natural numbers.
Related
Stated in
- Theorem 4.14 (Fundamental Theorem of Arithmetic)§4.3 Euclid’s Algorithm