Associated Topics || Dr. Math Home || Search Dr. Math

### Fermat's Little Theorem

```
Date: 09/02/2000 at 10:49:15
From: Isac Heden
Subject: Why is (n^p-n)/p always an integer?

Hello Dr. Math,

Can you help me prove that the expression n^p-n, where p is an
arbitrary prime and n is a positive integer, is always divisible by p?

I can prove it for p = 3 (and p = 2):

n^3-n = (n-1)n(n+1)

One of three factors must be divisible by three. And for p = 5:

n^5-n = n(n^2-1)(n^2+1) = (n-1)n(n+1)(n^2+1)

For a positive integer a; one of (n-1), n or (n+1) is divisible by 5
when n = 4+5a, n = 5+5a or n = 1+5a. The last factor (n^2+1) is
divisible by 5 when n = 3+5a and when n = 2+5a since the last digit is
always 2, 3, 7 or 8 and the last digit of n^2 always is 4 or 9. If you
add 1 to 4 or 9 you always obtain a number, whose last digit is either
5 or 0, and those numbers are divisible by 5.

Hence n^5-n can be divided by 5, for any integer n.

But I can't extend this proof, to apply for any prime, p, and that is
my problem.

Isac
```

```
Date: 09/05/2000 at 05:35:03
From: Doctor Floor
Subject: Re: Why is (n^p-n)/p always an integer?

Hi Isac,

Thanks for writing.

The theorem you mention is known as Fermat's Little Theorem.

For a proof we will do some modular arithmetic. Instead of (n^p-n)/p
being an integer, or n^p-n divisible by p, we will write:

n^p == n (mod p)

which is read as "n^p is congruent to n modulo p." It means that n^p
and n differ by a multiple of p. So, for example, 2 == 27 (mod 5) and
275 == 0 (mod 5).

There are some interesting properties of this modular arithmetic:

If a == b (mod m) and c == d (mod m), then also

a + c == b + d (mod m)
a - c == b - d (mod m)
a * c == b * d (mod m)

Division is a bit more difficult:

If the GCD of t and m is 1, and if ta == tb (mod m), then
a == b (mod m).

Now on to prove Fermat's Little Theorem:

n^p == n (mod p)

If n is divisible by p, then it is clearly true.

If n is not divisible by p, then the GCD of n and p is 1.

We note that for such n there are the following possibilities:

n == 1 (mod p)
n == 2 (mod p)
:
n == p-1 (mod p)

All numbers == 1 (mod p) are said to be in the "residue class of 1
modulo p."

So the numbers 1, 2, ... , p-1 represent all but one (the == 0 residue
class) residue classes modulo p. These p-1 residue classes are exactly
the residue classes representing numbers with a GCD of 1 with p.

Now if we multiply all these representatives of these p-1 residue
classes by n, we get n*1, n*2, ... , n*(p-1). No two of these numbers
can be in the same residue class modulo p, because if n*x == n*y (mod
p) then x == y (mod p) (see above). But then these numbers n*1, n*2,
..., n*(p-1) again represent all p-1 residue classes. Multiplying, we
get:

n*1 * n*2 * ... * n*(p-1) == 1 * 2 * ... * (p-1) (mod p)

Divide by 1*2*...*(p-1), which has a GCD of 1 with p, to get:

n^(p-1) == 1 (mod p)

and then multiply both sides by n and we have:

n^p == n (mod p)

as desired.

If you need more help, just write back.

Best regards,
- Doctor Floor, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/