Here is the proof for the A level style question puzzle. I am going to
talk about two approaches to this question which I enjoy. The first is proof by
induction and the second is modular arithmetic.
However, before we get on to those ideas we can make the puzzle simpler.
The expression n5-n can easily be factorised, by using the
differences of two squares as below.
n5-n = n(n4-1)
=n(n2+1)(n2-1)
=n(n+1)(n-1)(n2+1)
This already helps us a lot. We have to prove that expression always
divides by 30. Another way of doing that is proving that it always divides by
30’s prime factors, which are 2,3 and 5. This relies on composite numbers
having unique prime factorisation which we know is true. (That may be a good
topic for another post) In the expression n(n+1)(n-1)(n2+1) we have
three consecutive numbers making up terms. These are n-1 , n ,n+1. Every third
number divides by three and every second number divides by two. Therefore, if you
have a string of 3 consecutive number you know one of these will divide by three
and at least one will divide by two. This means the proof can now be reduced to
prove n5-n is divisible by 5.
Proof by Induction
Proof by induction is one of the most important tools in a mathematician’s
toolkit. The logical argument for a proof by induction is that if we
can prove something is true for all the numbers then it is true for the next
number n. if we have such an argument the fact it is true for the number 1
implies it is true for the numbers 1 and 2. Then the fact it is true for the
numbers 1 and 2 will imply it is true for the number 3 and so on indefinitely.
To conduct a proof by induction we need to prove two things: firstly, that the
assertion is true for the number 1 and secondly that if it is true for one it
is true for all integers. If we don’t have the first part the proof is not
valid, it is a strict if, then argument. We can then say the proof is true for all the
natural numbers.
Sadly, I couldn’t get the necessary symbols to type the proof up, so I have
provided a picture of my paper copy of the proof. I must first mention that the
notation, a|b, means that b divides into a and the arrow means if, then.
The first thing I did was establish f(1) was true. If you were wondering, strictly 5 does divide into 0, every number strictly does.
I then continue onto a lemma. This is pivotal because it tells us how to
get from f(n) to f(n+1) which we base the proof on. The statement f(n+1)-af(n)|5
(for some value a) is a standard result. It just means that f(n+1) take away
something times by f(n) will divide by 5. There will always be a value of a for this independent
of f(n). I then expand out the expression. On line 5 of the lemma I then
factorise the expression. This clearly shows that when a=6 f(n+1)-af(n)|5. We
can now move onto the main proof.
We are still working on an if, then statement so the proof goes if f(n)|5
then 6f(n)|5. This is allowed because, if a|b then xa|b for all integer values
of x. The third line down we can write from the lemma. Any number divisible by 5 add
another number divisible by 5 (which we got from the lemma) will still be
divisible by 5. This is generalised as if a|b and c|b then a+c|b. Clearly in
the proof the plus and minus 6f(n) cancel to leave the result, f(n+1) is divisible
by 5.
Therefore, we have proved the original statement that n5-n|30
for when n is a natural number.
Modular Arithmetic
At first modular arithmetic can seem quite an odd concept, but the range
of things we can solve using this way of thinking is remarkable. Modular arithmetic offers an alternative way
to look at our number system, instead of imagining numbers lying on a line, a
section of the number line is ‘rolled up’ to form a circle, much like a clock
face. Once the time reaches 12 o’clock, it becomes not 13 but 1 o’clock, and
continues around the cycle as before. Under this system, it could be said that
12 + 1 =13 is essentially the same as 1, or that both 2 + 48 = 50 and 4 + 10 =
14 are essentially the same as 2. In fact, many numbers could be said to be
essentially the same if the time of day doesn’t matter, If a number other than
12 is chosen, the same idea should follow, but the sets of equivalent numbers
are arranged differently. As shown below.
In mathematics this idea of many numbers occupying the same place on the
clock has been formalised and condensed into a more workable form by
introducing the concept of congruence
to take the place of numbers being effectively the same and naming the number
of hours on the clock as the modulus. I would encourage research on modular arithmetic, it can do some fascinating things but I will now explain its relevance to the
proof.
One law that arises from modular arithmetic is that, mod m, if two congruencies
of two different numbers are the same, when you take them away from each other
the result will always divide by m. Therefore, if we can show that n5 and
n are the same for 0,1,2,3,4,5, all the numbers up to 5 (mod 30) it proves that n5-n|5.
I produced the table below
r N5 n
0 0 0
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
Hence, we have now proved that n5-n|5. Therefore, we know
that n5-n|30
I hope you enjoyed that puzzle the next puzzle will be online soon. Thank you again for reading
