Republic of Mathematics blog

How do I prove that 5 divides x^5 – x? The joys of modular arithmetic

Posted by: Gary Ernest Davis on: February 11, 2010

On Physics Forums , ninjagod123 asked:

“How do I prove that 5 divides x^5 - x??”

In this question, the variable “x” should be thought of as restricted to integer values – in fact positive integer values – since divisibility for fractions or real numbers in general is trivial.

So another way to ask the question is: if x is a positive integer, how do we see that x^5-x is always a multiple of 5?

First thought is to factor an x in  x^5-x to get x(x^4-1).

The reason this is suggestive is because 5 is a prime number , so if 5 divides  x(x^4-1) then either 5 divides x or 5 divides x^4-1.

So now the question becomes, if 5 does not divide x, why does 5 divide x^4-1?

We can think of this in terms of arithmetic modulo 5, where we only keep remainders after division by 5.

In the language of modular arithmetic, the question is:

if x\neq 0 (mod 5) is x^4-1= 0 (mod 5)?

x\neq 0 (mod 5) means x gives a remainder of 1, 2, 3 or 4 after division by 5 , so there are 4 cases to consider.

How about the other way around:

if x^4-1\neq 0 (mod 5) is x =0 (mod 5)?

x^4-1\neq 0 (mod 5) means x^4 \neq 1 (mod 5)

What are the 4^{th} powers of integers modulo 5?

x x^4 x^4 (mod 5)
0 0 0
1 1 1
2 16 1
3 81 1
4 256 1

So this little table tells us that the only time x^4 \neq 1 (mod 5)

is when x is itself a multiple of 5.

This simple little argument shows the power of working with remainders after whole number division – which is just modular arithmetic.

Fermat’s little theorem

Piere de Fermat stated, and Euler and others proved, a useful little gem of number theory, known as Fermat’s little theorem.

It states that if p is a prime number then for all integers x, x^p = x(mod p).

Since 5 is a prime number, the result above is just a special case of Fermat’s little theorem.

This page has a number of different proofs of Fermat’s little theorem.

2 Responses to "How do I prove that 5 divides x^5 – x? The joys of modular arithmetic"

Are we allowed to use mathematical induction?

I don’t think anyone’s stopping you, are they?

Leave a Reply