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

On Physics

“How do I prove that 5 divides ??”

In this question, the variable “” 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 Â is a positive integer, how do we see that is always a multiple of 5?

First thought is to factor an Â in Â to get .

The reason this is suggestive is because 5 is a prime number , so if 5 divides Â then either 5 divides Â or 5 divides .

So now the question becomes, if 5 does not divide , why does 5 divide ?

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 Â is ?

means 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 is ?

means

What are the 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

is when Â 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.

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 is a prime number then for all integers , .

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.

1 | fair_numbers

October 14, 2010 at 9:12 pm

Are we allowed to use mathematical induction?

Gary Davis

October 15, 2010 at 5:28 am

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