Over 2,300 years ago, Euclid proved the Fundamental Theorem of Arithmetic. Now it is our turn.

Statement of the Theorem

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.

Proof

Part I: Bezout’s Lemma

Bezout’s lemma tells us that, if two numbers a and b share no prime factors other than 1 and -1, then we can find q and s such that qa+sb=1.

Ok, let’s take some time to digest that with a worked example. Consider 7, and 9. The only numbers with divide 7 are {7,1,-1,-7}. The only numbers which divide 9 are {9,3,1,-1,-3,-9}. So, 7 and 9 share no prime factors. Our task is now to find two numbers q and s such that 7q + 9s = 1.

Well, we could guess a few numbers, and perhaps we find that 9*3 = 27, and 7*4 = 28. So we could try q=4, and s=-3. Then:

7*4–9*3 = 1.

Bezout Lemma Proof

My note: if you get really stuck on the proof of Bezout’s Lemma, then it’s ok to skip to the next section. Try and get a feel for why it works even if you don’t understand every detail.

Previously I guessed a few numbers until I found that 7*4–9*3=1.

However, guessing doesn’t prove things in general . We now prove the result again for the case of 7 and 9, but ‘pretend’ we haven’t just guessed the result, and find it systematically. This systematic method works on all numbers!

We use the Euclidean Algorithm. That means we use division with remainder to find the greatest common divisor of two numbers, which in our case is 1. Then, we reverse the steps of the algorithm to prove we can write 1 as a combination of 9’s and 7’s.

Take 7 and 9.

9 = 7 + 2

7 = 3*2 + 1

We then want to rebuild 1 in terms of 7’s and 9’s. We do this as follows:

1 = 7–3*2

1 = 7–3(9–7)

1=7–3*9 +3*7 = 4*7–3*9

Do you see how we ‘break down’ our two numbers to produce a 1, and then rebuild ‘1’ using 7’s and 9’s from the pieces. Let’s see this in action again.

This time our numbers are 49 and 51.

51 = 49 + 2

49 = 2*24 + 1

Now we reconstruct:

1 = 49–2*24

1 = 49–24(51–49)

1 = 25*49–24*51

Given any two numbers which don’t share a factor, we can go through the same process, just potentially with more steps. We do one final example.

Our numbers are 99 and 35.

99 = 2*35 + 29

35 = 29 + 6

29 = 4*6 + 5

6 = 1*5 + 1

Now we reconstruct:

1 = 6–5

1=6-(29–4*6) = 5*6–29

1=5*(35–29) — 29 = 5*35 -6*29

1=5*35 — 6*(99–2*35)=17*35–6*99

Part II: Euclid’s Lemma

Euclid’s lemma says that if a prime number p divides x times y, then p divides x, or p divides y (and potentially both).

For example, 3 divides 3465=99*35. Euclid’s lemma says that 3 divides 99, or 3 divides 35. We can see that 3 divides 99, as 99=3*33

Suppose p divides xy, but that p doesn’t divide x. Then, by Bezout’s Lemma, we can find a t, s such that:

t*p + s*x = 1

Then, multiply through by y:

t*p*y + s*x*y = y.

Divide by p:

t*y +s*xy/p = y/p

As xy/p is an integer, we deduce that y/p is an integer, and therefore p divides y.

We repeat these steps with a worked example. Say we know that 3 divides 99*35, as 35*99=3*1155, but doesn’t divide 35. Then:

12*3 +35(-1) =12*3 -35 = 1

12*3*99 -35*99 = 99.

12*99–35*99/3 = 99/3

As we know 35*99/3 is an integer, we therefore know 12*99–35*99/3 is an integer. And so 3 divides 99.

Part III: Bringing it all together

Existence

First we need to show that, given a number, we can write it as a product of primes. Take a number N. Suppose that all smaller numbers can be written as a product of primes. If no number smaller than N divides it, then N itself is prime. Otherwise, if a smaller number divides it, say, N = ab, we can write a and b as a product of primes, and therefore we can write N as a product of primes.

As we did previously, we give a worked example to go alongside this rather abstract proof. Suppose we know that {2,3,4,5,6,7,8,9,10,11} can all be written as the product of primes. Then, we write 12 = 6*2. As we know that 6 can be written 3*2, we conclude that 12=3*2*2. Therefore knowing that the first 11 integers can be written as the product of primes allows us to prove that the 12th can be written as a product of primes. Once we know that 12 can be written as a product of primes, as we can prove that 13 can be written as a product of primes.

This is known as strong induction, where knowing that some property for all previous cases (in this case, being able to write a number as the product of primes) allows us to prove that the next number, N+1, has that property (i.e. can be written as the product of primes)

Uniqueness

Finally we prove uniqueness. It’s not enough to prove that we can write a number as the product of primes, we also want to show that there is only one way of doing so.

First we do a worked example of what will be a somewhat abstract argument.

Suppose someone claimed that 5*7²=7*11*3, and we wanted to prove this was false without explicitly calculating both sides. First, we divide both sides by 7, so that 7 doesn’t appear on both sides. Now the claim is tantamount to:

5*7=11*3

Now, by Euclid’s Lemma, we can prove this is impossible. This means that 5 divides 11*3. Therefore, 5 divides 11, or 5 divides 3. But these numbers are primes: the only numbers which divide them are themselves. So, this would imply that 5=11, or 5=3, which is patently absurd. Thus we can conclude that 5*7²=7*11*3 is a false statement.

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

Now we do the general proof.

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.

Thanks for taking the time to learn some math :) I’m Ethan. I studied Part I and Part IIa Economics at Cambridge and have now switched to Part Ib Mathematics. My twitter is ethan_the_mathmo where I will occasionally share some math and other updates.

If you have any thoughts, questions, or feedback, please feel free to leave it in the comments section :)

Mathematics