1 April, 2013

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.

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

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**).

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
**p**of_{1}**n**. - If
**p**is equal to_{1}**n**then we're done. - Otherwise, calculate
**n**=_{1}**n**÷**p**_{1} - Repeat the process with
**n**, until it's all factorised._{1}

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

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.

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) ...

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**.

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**)

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

The lemma that a product of two non-multiples of a prime **p** must be a non-multiple of **p**
can be stated alternatively as Euclid's lemma:

If a numberNis a multiple of a prime numberp, andN=a×b, then at least one ofaandbmust be a multiple ofp.

Mathematicians used to think that unique factorisation was true in any mathematical system which had the basic operations of addition, subtraction and multiplication, and a notion of prime numbers. But they eventually realised the importance of Euclid's Lemma, and its dependence on a notion of division by remainder, where the remainder is "smaller" in some sense that the divisor.

Systems with addition, subtraction and multiplication are called
**rings** (in saying that I have glossed over a few technical issues), and
one way to make interesting rings which are different from the ring of
integers is to **extend** the ring of integers by adding in the square
root of one particular number, like the square root of 2, or even the square
root of -1. (In an extension, you include the new number, and all
combinations of the new number via arithmetical operations with the existing
numbers.) You can also extend with cube roots, and other sorts of roots. Some
of these extensions have versions of Euclid's Lemma, which implies unique
factorisation into primes, and some of them have unique factorisation even
though they don't have Euclid's lemma, and some of them don't have unique
factorisation at all.