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.

Like this:

Be the first to like this post.

This entry was posted on November 21, 2009 at 10:35 pm and is filed under Cambridge Maths Tripos, IA Numbers & Sets, II Number Theory, Theorem. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

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

Theorem 15: Lagrange’s theorem about sums of four squares « Theorem of the week Says:
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 [...]
Theorem 30: Pythagorean triples « Theorem of the week Says:
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 [...]
NEERU Says:
August 17, 2010 at 8:09 pm
is 2*3*7*13+13 a prime. please answer now
theoremoftheweek Says:
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?
Ethaniel Says:
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
Theorem 5: the square root of 2 is irrational « Theorem of the week Says:
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 [...]
Number Theory: Lecture 2 « Theorem of the week Says:
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). [...]
Number Theory: Lecture 15 « Theorem of the week Says:
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 [...]

Theorem of the week