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:
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:
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:
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:
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:
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:
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:
For example, to factorise 490:
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:
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.:
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:
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 number N is a multiple of a prime number p, and N = a × b, then at least one of a and b must be a multiple of p.
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.
