I’ve mentioned the fundamental theorem of arithmetic a few times on this blog, so it’s probably time for it to be a theorem of the week. I’ll state it straightaway.

Theorem (the fundamental theorem of arithmeticEvery integer greater than 1 can be expressed as a product of primes, uniquely up to reordering the factors.

For example, , and while I can also write it as , this is just reordering the factors — it’s not a genuinely different factorisation. Prime numbers also have prime factorisations: the prime factorisation of 17 is simply 17.

Note that the fundamental theorem of arithmetic is one good reason why it’s convenient to define 1 not to be a prime. If it were prime, we could add as many factors of 1 as we liked to the prime factorisation of a number to get lots of different (but not interestingly different) factorisations.

This is a really important theorem — that’s why it’s called “fundamental”! It tells us two things: existence (there *is* a prime factorisation), and uniqueness (the prime factorisation is unique). Both parts are useful in all sorts of places. The existence part is useful because it tells us that the primes are somehow the “building blocks” of the integers, and this helps with lots of things. The uniqueness part is useful because it allows us to do certain things that would otherwise not be possible. For example, if we know the prime factorisation of , then we know the prime factorisation of , safe in the knowledge that can’t also have some other prime factorisation.

### A useful lemma

Before I tell you about a proof of this theorem, there’s a preliminary result that we’ll need. It’s jolly useful in all sorts of places.

LemmaLet be a prime, and suppose that divides the product . Then divides or divides .

(As usual in mathematics, the “or” here is inclusive, in the sense that we could have dividing both and .)

This really is a property of primes. For example, 6 divides , but 6 divides neither 3 nor 4. (Intuitively, I like to think that this is because we can break up 6 into , and the factors here can divides the factors 3 and 4 separately.) In fact, this property is sometimes taken as the *definition* of a prime number. In that case, one would then show from this definition that a prime number can be divided only by itself and 1. But since most people are more familiar with the definition of a prime as a number divisible only by itself and 1, I’m going to stick with that definition and show you how to prove the lemma. I’m going to use Bézout’s theorem, so if you don’t know that result you might like to read about it now (and then come back here afterwards!).

**Proof of lemma** We have a prime , and we know that it divides the product . Let’s suppose that doesn’t divide . Then our goal will be to show that divides .

Now if doesn’t divide , then and are coprime. As usual, we try using Bézout’s theorem to turn this into a positive statement: there are integers and such that .

We know that divides , so we should try to get something containing . Let’s multiply our equation by : we get .

Now divides each term on the left-hand side, so it must divide the right-hand side. That is, divides , as we wanted.

### Proof of the theorem

Now we are well placed to tackle the proof of our main theorem, the fundamental theorem of arithmetic. We’ll do the two parts (existence and uniqueness) separately.

**Existence** We need to show that every integer greater than 1 has a prime factorisation. To do this, we shall use the idea of a minimal counterexample. If the result isn’t true, then there must be a smallest number that doesn’t have a prime factorisation. Let’s call it .

Now can’t be prime, because if were prime then it would have a prime factorisation: itself. So is composite. That is, it is a product of two smaller numbers, say .

Then and are less than , and is the smallest number not having a prime factorisation, so and must have prime factorisations. But then has a prime factorisation: simply multiply those of and .

So there can’t be a counterexample, so the result must be true.

**Uniqueness** Now our job is to show that every integer greater than 1 has a *unique* prime factorisation.

So let’s suppose that we have a number with two factorisations: . Here , …, , , …, are primes, not necessarily distinct (we can have or whatever). Our aim is to show that in fact these two factorisations are the same.

If any is equal to some , then we can cancel those factors. Let’s do that wherever possible. We hope that in fact we now have no primes left on either side, because then we’ll know that the two factorisations were the same (they contained exactly the same primes). So let’s suppose that isn’t the case and try to obtain a contradiction.

We have something like , where each is not equal to any .

Now divides the right-hand side, so it must divide the left-hand side too. Using our lemma repeatedly, we see that means that divides for some . But and are both prime, so this says that — and we’ve assumed that not to be the case.

This gives the contradiction we wanted, so the factorisation is indeed unique.

### Further reading

Of course, Wikipedia has a page about the fundamental theorem of arithmetic. The theorem should be described in any decent introduction to number theory. As usual, I shall mention Davenport’s *The Higher Arithmetic* at this stage.

It turns out that there are settings (number fields) in which one can do number theory, but where one does not necessarily have unique factorisation. This leads to a lot of extremely interesting mathematics — perhaps I shall return to it in a future theorem of the week. There’s so much interesting maths out there!

January 27, 2010 at 10:57 pm

[…] that it’s enough to show that every prime is the sum of four squares. Why? Well, the Fundamental Theorem of Arithmetic tells us that every positive integer is a product of primes. If we know that primes are sums of […]

June 27, 2010 at 6:47 pm

[…] and also divides and so — but that contradicts our assumption that , and are coprime.) Unique factorisation then allows us to conclude that and are squares, say and […]

August 17, 2010 at 8:09 pm

is 2*3*7*13+13 a prime. please answer now

August 17, 2010 at 9:06 pm

Well, what would it mean for it to be a prime? It would mean that it doesn’t have any factors other than itself and 1. Is that the case? Can you see any factors of this number other than itself and 1?

July 15, 2011 at 3:00 pm

2*3*7*13+13 = (2*3*7+1)*13 = N*13 => the number is not a prime

August 15, 2011 at 11:51 am

[…] , so they must have the same prime factorisation (by the Fundamental Theorem of Arithmetic). But we’ve just established that the powers of 2 are different! This is the […]

October 10, 2011 at 12:03 pm

[…] Theorem 6 (Fundamental Theorem of Arithmetic): Let be a natural number. Then can be factorised as a product of primes, in an essentially unique way. (Remember that we do not count different orderings of the same factors as different factorisations. With the phrasing here, we consider 1 as being factorised into the ‘empty product‘. If you prefer, simply state the result for .) Proof of existence using induction (very similar to Lemma 1), and uniqueness using the previous result (about primes dividing products). […]

November 9, 2011 at 12:15 pm

[…] by considering the ‘partial product’ . Note that this result essentially records the fundamental theorem of arithmetic. This Euler product is crucial for linking the zeta function to the […]

July 15, 2012 at 4:40 pm

so good……..

August 16, 2012 at 11:47 am

[…] talked about Euclid‘s algorithm and Bézout‘s lemma. In the second, we mentioned the Fundamental Theorem of Arithmetic, and we learned about modular arithmetic. In the third and final lecture, we mentioned that is […]

August 15, 2013 at 9:11 am

[…] we talked about Euclid‘s algorithm and Bézout‘s lemma. In the second, we mentioned the Fundamental Theorem of Arithmetic, and we learned about modular arithmetic. In the third and final lecture, we mentioned that is […]

October 11, 2013 at 11:18 am

[…] Theorem 6 (Fundamental Theorem of Arithmetic): Let be a natural number. Then can be written as a product of primes, in an essentially unique way. Existence follows by induction, uniqueness using Proposition 5. […]