Theorem 13: the fundamental theorem of arithmetic

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 arithmetic Every integer greater than 1 can be expressed as a product of primes, uniquely up to reordering the factors.

For example, 12 = 2\times 2\times 3, and while I can also write it as 12 = 2\times 3\times 2, 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 n, then we know the prime factorisation of n^2, safe in the knowledge that n^2 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.

Lemma Let p be a prime, and suppose that p divides the product ab.  Then p divides a or p divides b.

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

This really is a property of primes.  For example, 6 divides 3\times 4, but 6 divides neither 3 nor 4.  (Intuitively, I like to think that this is because we can break up 6 into 2\times 3, 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 p, and we know that it divides the product ab.  Let’s suppose that p doesn’t divide a.  Then our goal will be to show that p divides b.

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

We know that p divides ab, so we should try to get something containing ab.  Let’s multiply our equation by b: we get bph + abk = b.

Now p divides each term on the left-hand side, so it must divide the right-hand side.  That is, p divides b, 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 n.

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

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

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 n with two factorisations: n = p_1 \dotsm p_k = q_1 \dotsm q_l.   Here p_1, …, p_k, q_1, …, q_l are primes, not necessarily distinct (we can have p_1 = p_3 or whatever).  Our aim is to show that in fact these two factorisations are the same. 

If any p_i is equal to some q_j, 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 p_1 \dotsm p_r = q_1 \dotsm q_s, where each p_i is not equal to any q_j.

Now q_1 divides the right-hand side, so it must divide the left-hand side too.  Using our lemma repeatedly, we see that means that q_1 divides p_i for some i.  But q_1 and p_i are both prime, so this says that q_1=p_i — 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!

Advertisements

12 Responses to “Theorem 13: the fundamental theorem of arithmetic”

  1. Theorem 15: Lagrange’s theorem about sums of four squares « Theorem of the week Says:

    […] 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 […]

  2. Theorem 30: Pythagorean triples « Theorem of the week Says:

    […] 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 […]

  3. NEERU Says:

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

  4. theoremoftheweek Says:

    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?

  5. Ethaniel Says:

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

  6. Theorem 5: the square root of 2 is irrational « Theorem of the week Says:

    […] , 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 […]

  7. Number Theory: Lecture 2 « Theorem of the week Says:

    […] 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). […]

  8. Number Theory: Lecture 15 « Theorem of the week Says:

    […] 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 […]

  9. komal dhing Says:

    so good……..

  10. Sutton Trust summer school 2012 « Theorem of the week Says:

    […] 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 […]

  11. Sutton Trust summer school 2013 | Theorem of the week Says:

    […] 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 […]

  12. Number Theory: Lecture 1 | Theorem of the week Says:

    […] 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. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: