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/