# a blog about things that I've been thinking hard about

# Proof of Unique Factorisation by Primes (v2)

1 April, 2013
This is my second attempt to give an easy-to-read proof of Unique Factorisation into Primes (otherwise known as the Fundamental Theorem of Arithmetic).
by Philip Dorrell

## Definition of Factor and Multiple

A factor of a natural number n is a number f such that some other number g can be multiplied by f to get n.

For example, 5 is a factor of 35 because:

5 × 7 = 35

If f if a factor of n, then we also say that n is a multiple of f. So 35 is a multiple of 5.

1 is a factor of every natural number n, and every non-zero natural number n is a factor of itself, because:

1 × n = n

It follows that every natural number n is a multiple of 1 and a multiple of itself.

## Definition of Prime Number

A prime number is a natural number which does not have any factors other than 1 and itself.

In other words, the only multiplication whose result is a prime number p is:

1 × p = p

For example, 7 is a prime, because 1 × 7 is the only way to multiply two natural numbers to get the result 7.

And 12 is not a prime, because:

3 × 4 = 12

## Every natural number greater than 1 has at least one prime factor

I will prove this constructively, which means I will give instructions how to find a prime factor for any natural number n ≥ 2.

The instructions are:

- Start with a trial factor f set to 2.
- By doing a division with remainder, check if the trial factor is a factor of n.
- If the trial factor is not a factor, increase it by 1,
- Repeat this until a factor is found.

The repetition must come to an end when f reaches the value of n, since every number is a factor of itself.

Also, the first factor f found must be a prime number, because a factor of a factor is itself a factor. If g is a factor of f smaller than f, and f is a factor of n, then g is a factor of n and it would have been found first.

For example, searching for a prime factor of 385, we wouldn't find 35, because 35 = 5 × 7, and we would have found 5 first as a factor of 385 (if indeed there wasn't some other prime factor of 385 smaller than 5).

## Every natural number greater than 1 can be completely factorised into prime numbers

For example, 3400 can be factorised as follows:

3400 = 2 × 2 × 2 × 5 × 5 × 17

where 2, 5 and 17 are prime numbers.

Given the instructions I've already given for finding at least one prime factor of a number n, the instructions for completely factorising n into primes are:

- Find a first prime factor p1 of n.
- If p1 is equal to n then we're done.
- Otherwise, calculate n1 = n ÷ p1
- Repeat the process with n1, until it's all factorised.

For example, to factorise 490:

- The first prime factor is 2
- 490 ÷ 2 = 245
- The first prime factor of 245 is 5
- 245 ÷ 5 = 49
- The first prime factor of 49 is 7
- 49 ÷ 7 = 7
- The first prime factor of 7 is 7
- Therefore, 490 = 2 × 5 × 7 × 7

## Uniqueness of Factorisation

We've now shown that every natural number greater than 1 has a factorisation into primes. But a big question is: can there be two different ways to factorise a number into primes?

Now we know that we can change the order of multiplication, so, for example:

490 = 2 × 5 × 7 × 7 = 7 × 2 × 5 × 7

So we want to say that doing it in a different order doesn't count.

In other words, we want to know: can there be two different ways to factorise a number into primes where the second factorisation isn't just the first factorisation with the factors in a different order?

The particular instructions I've given to factorise a number will always give the same result. But actually, we could change that algorithm by finding all the prime factors of a number at each step, and then, at each step, randomly choosing one of those factors as the next factor. It's possible (we don't know yet) that for some number n, this changed algorithm might result in a different factorisation, which isn't just a re-ordering of the lowest-prime-factor-first factorisation.

## A Possible Non-Unique Factorisation

We want to consider a possible non-unique prime factorisation of some number n.

There are two different prime factorisations, and the second factorisation isn't just the first one in a different order.

It might be that the two different factorisations have some prime factors in common.

What we can do is divide each factorisation by any common prime factors, until we get some smaller number n' which has two different prime factorisations that don't have any prime factors in common.

From this factorisation, we can choose any prime factor, for example we can choose a prime factor p from the first factorisation, and then we can look at the second factorisation. Because of the reduction we did, p is not in the second factorisation, and because a prime number cannot be a factor or multiple of any other prime number, none of the prime factors in the second factorisation can be multiples of p.

Which leads to the question: can a product of non-multiples of a prime number p be a multiple of p?

It is sufficient to consider the case of the product of two non-multiples of p. Because if the product of two non-multiples is a non-multiple, then the product of any number of non-multiples must still be a non-multiple.

So, we want to prove the following lemma (a "lemma" is a mini-theorem within the proof of a theorem which helps us to prove the main theorem that we want to prove) ...

## Lemma: the Product of Two Non-Multiples of a Prime p is a Non-Multiple of p

So let us consider two numbers a and b which are non-multiples of p such that a × b is equal to a multiple of p, i.e.:

a × b = m × p

for some number m.

### Descent

There are two different types of descent that we can apply to this equation. ("Descent" is when we have an example of something, and we use it to find a example of the same thing which is in some sense "smaller" or "lower" than the original example.)

The first is that if a is greater than p, then we can replace a with a - p and we can replace m with m - b and the equation will remain true. Similarly we can replace b with b - p if b is greater than p. If we apply these steps repeatedly, we will end up with values for a and b which are less than p. (The end result is the same as if we had divided each of a and b by p and replaced them by their remainders.)

The second type of descent is to find a similar equality for a prime q which is smaller than p.

We can start by choosing the lowest prime factor q of either a or b. Assume for the sake of argument that it is a factor of a (if it isn't we can just swap a and b first, and then proceed with the same argument).

If m is also a multiple of q, then we can divide both a and m by q.

We can continue this procedure, until we find some prime factor r which is a factor of a and which is not a prime factor of m.

Given that m and p are non-multiples of r, we now have a prime r such that two non-multiples of r multiply to make a multiple of r, and r is smaller than p (since r is smaller than a and a is smaller than p).

This technique of finding smaller values from a value with a particular property is called the method of infinite descent. (The descent is "infinite", because we can repeat it indefinitely. If the amount of "room" available for descent is finite, then the infinite descent will have to come to a stop somewhere, and we will arrive at some sort of contradiction.)

In this case, we could have chosen p to be the smallest prime for which there are two non-multiples which multiply to a multiple of p. (By choosing the lowest such p, we have already "descended" to the lowest possible place in our "descent".) In which case we have found another r with the same property which is smaller than p, which is impossible because p is meant to be the smallest. Therefore there can be no such p in the first place, and we can deduce that the product of non-multiples of any prime p must be a non-multiple of p.

QED (which means we have proved what we set out to prove, in this case the lemma that the product of two non-multiples of a prime p is also a non-multiple of p)

## And in conclusion ...

Now that we have proved the lemma, we can revisit the main theorem:

- We had two prime factorisations of a number n', each with no prime factors in common.
- We then chose one prime factor p from the first factorisation.
- All of the prime factors in the second factorisation are non-multiples of p.
- According to the lemma, the product of non-multiples of any prime p must be a non-multiple of p
- Therefore the product of primes in the second factorisation must be a non-multiple of p
- Which is a contradiction, because the product of primes in the first factorisation is a multiple of p (since p is one of the prime factors in that factorisation)
- QED for the main theorem

Vote for or comment on this article on Reddit or Hacker News ...