Fundamental theorem of arithmetic

The **Fundamental theorem of arithmetic** (also called the **unique factorization theorem**) is a theorem of number theory. The theorem says that _every_ positive integer greater than 1 can be written as a product of prime numbers (or the integer is itself a prime number). The theorem also says that there is only one way to write the number. If two people found two different ways to write the number, the only thing that can be different is the order in which the primes are written. For example, we can write:

- 6936 = 2<sup>3</sup> · 3 · 17<sup>2</sup>   or   1200 = 2<sup>4</sup> · 3 · 5<sup>2</sup>

and if somebody else finds _another_ way to write 6936 or 1200 as product of prime numbers, we can put those prime numbers in the right order and find out that it is the same as what we have here. Finding the prime numbers is called factorization.

This theorem can be used in cryptography.

## Proof

The first person who proved the theorem was Euclid. The first detailed and correct proof was in the _Disquisitiones Arithmeticae_ by Carl Friedrich Gauss.

Some people may think that the theorem is true everywhere. However, the theorem is _not_ true in more general number systems, like algebraic integers. This was first mentioned by Ernst Kummer in 1843, in his work on Fermat's last theorem. For more information about that: read algebraic number theory.

The proof consists of two parts: _first_ we show that every number can be written as a product of primes; _second_ we show that if we write a number as a product of primes for a second time, then the two lists of prime numbers must be the same.

### First part of the proof

We show that if _not_ every number greater than 1 can be written as a product of primes, we end up in some kind of impossibility. So after that we conclude that it _must_ be true that every number can be written as a product of primes.

So, now see what happens when somebody says that they know a positive integer, greater than 1, which can _not_ be written as a product of primes. In that case we ask them to mention _all_ the numbers, greater than 1, that can _not_ be written as a product of primes. One of these numbers must be the _smallest_: let's call it _n_. Of course, this number _n_ cannot be 1. Further, it cannot be a prime number, because a prime number is a 'product' of a single prime: itself. So it _must_ be a product of numbers. Thus-

- _n_ = _ab_

where both _a_ and _b_ are positive integers that are of course smaller than _n_. But: _n_ was the _smallest_ number that can not be written as a product of primes. So it must be possible to write _a_ and _b_ as products of primes, because they are both smaller than _n_. But then the product

- _n_ = _ab_

can be written as a product of primes as well. This is an impossibility because we said that _n_ can not be written as a product of primes.

We have now shown the impossibility which exists if the first part of the theorem would not be true. In this way we have now proven the first part of the theorem.

### Second part of the proof

Now we have to prove that there is only one way to write a positive number greater than 1 as a product of prime numbers.

To do this, we use the following lemma: if a prime number _p_ divides a product _ab_, then it divides _a_ or it divides _b_ (Euclid's lemma).
First we now prove this lemma. Well, assume now that _p_ does not divide _a_. Then _p_ and _a_ are coprime and we have Bezout's identity that says that there must be integers _x_ and _y_ such that

- _px_ + _ay_ = 1.

Multiplying everything with _b_ gives

- _pbx_ + _aby_ = _b_,

Remember that _ab_ could be divided by _p_. So now, on the left-hand side we have two terms that are divisible by _p_. So the term on the right-hand side is also divisible by _p_. We have now proven that if _p_ does not divide _a_, it must divide _b_. That proves the lemma.

Now we will prove that we can write an integer greater than 1 in _only one_ way as a product of prime numbers.

Take a number _N_. Let's say _N_ can be written as a product of primes in two different ways, say _P_ and _Q_.

_N = P = Q_

_p<sub>1</sub> * p<sub>2</sub> * p<sub>3</sub> * p<sub>4</sub> * p<sub>5</sub> ... = q<sub>1</sub> * q<sub>2</sub> * q<sub>3</sub> * q<sub>4</sub> * q<sub>5</sub> ..._

We know that since _p<sub>1</sub>_ divides _P_, it also has to divide _Q_. However, since all the factors in _Q_ are primes, _p<sub>1</sub>_ must be included in _Q_. Now let us remove _p<sub>1</sub>_ from _P_ and _Q_. We get two new products, and we can keep repeating this until both sides are reduced to _1 = 1_.

Since we reduced both sides by removing the same factors, both sides must be the same, so the prime factorization must be unique.

## Related pages

- Fundamental theorem of algebra