Posts
Over 2,300 years ago, Euclid proved the Fundamental Theorem of Arithmetic. Now it is our turn by Maths and Musings published in Cantor’s Paradise.
Some surviving fragments from Euclid’s Elements
The Fundamental Theorem of Arithmetic states that we can decompose any number uniquely into the product of prime numbers. For example, 350 = 2*7*5², and there is no other way to write 350 as the product of prime numbers...
Suppose we can write a number as the product of primes in two ways. If there are any primes which appear on both sides, divide appropriately so that the two factorisations share no primes.
Take our first prime, ‘p_1’. Clearly p_1 divides N. Now, as p_1 divides N, p_1 divides the second prime factorisation. By (repeated application of) Euclid’s Lemma, this means that p_1 divides one of the prime factors of N. But as these numbers are prime, p_1 must equal one of the prime factors. This is a contradiction, as we had already cancelled out all the shared prime factors.
Thus, the factorisation into primes must be unique.
Source: Medium
