Fermat's Little Theorem: A Special Case

Date: 06/26/2001 at 02:40:51
From: saquib mukarram
Subject: Induction

Show that n^7-n is divisible by 7.

Date: 06/26/2001 at 05:00:58
From: Doctor Pete
Subject: Re: Induction

Hi,

Although the subject of your message is "induction," your problem can 
be solved instead by using congruences. We say that two integers a, b 
are congruent modulo m, if a-b is divisible by m. For example, 8 and 
24 are congruent modulo 4 because 8-24 = -16, which is divisible by 4. 
This can also be written as a == b (mod m), which means "a is 
congruent to b modulo m."  Clearly, if

     a == b (mod m),
then
     b == a (mod m),
and
     ca == cb (mod m),
and
     a + c == b + c (mod m).

where c is any integer.

Now, clearly every integer n is congruent to either 0, 1, 2, 3, 4, 5, 
or 6 (mod 7). In other words, when a number n is divided by 7, the 
remainder is either 0, 1, 2, 3, 4, 5, or 6. Therefore, let us consider 
the following:

     n^7 - n = n(n^6 - 1)
             = n(n^3-1)(n^3+1) 
             = n(n-1)(n^2+n+1)(n+1)(n^2-n+1),

so if n, n-1, or n+1 is divisible by 7, then n^7-n is divisible by 7.  
Thus, the cases where n == 0, 1, or 6 (mod 7) implies n^7 - n == 0 
(mod 7). What about the other cases; i.e., n == 2, 3, 4, 5 (mod 7)?  
Well, we see that

     n == 2 (mod 7)    implies     n^2 == 4 (mod 7),
     n == 3 (mod 7)    implies     n^2 == 9 == 2 (mod 7),
     n == 4 (mod 7)    implies     n^2 == 16 == 2 (mod 7),
     n == 5 (mod 7)    implies     n^2 == 25 == 4 (mod 7).

Thus, n^2 + 1 == 3 (mod 7) if n == 3 or 4 (mod 7), which means that

     n^2 - n + 1 == 0 (mod 7) if n == 3 (mod 7),
and
     n^2 + n + 1 == 7 == 0 (mod 7) if n == 4 (mod 7).

Similarly, n^2 + 1 == 5 (mod 7) if n == 2 or 5 (mod 7); hence

     n^2 - n + 1 == 0 (mod 7) if n == 5 (mod 7),
and
     n^2 + n + 1 == 7 == 0 (mod 7) if n == 2 (mod 7).

It follows that n^7 - n is divisible by 7 for all integers n.

For an induction proof (which is more elegant), consider the case 
where n = 1:  We have

     n^7 - n = 1^7 - 1 = 0,

which is divisible by 7. Now, suppose there exists a number k for 
which k^7 - k is divisible by 7. We will show that this implies 
(k+1)^7 - (k+1) is also divisible by 7. For

(k+1)^7 - (k+1) = k^7 + 7k^6 + 21k^5 + 35k^4 + 35k^3 + 21k^2 + 7k - k.

By the induction hypothesis, the first and last term, k^7 - k, is 
divisible by 7. And clearly, all the other terms are divisible by 7; 
hence the entire expression is divisible by 7. Thus (k+1)^7 - (k+1) is 
divisible by 7 if k^7 - k is divisible by 7. Therefore n^7 - n is 
divisible by 7.

This problem is interesting, because it is a special case of what is 
known as Fermat's Little Theorem, which states that for a given prime 
p,
       x^p == x (mod p),

for all integers x. Your problem is equivalent to the case p = 7. You 
might be able to see why this is true, if you look at the inductive 
proof I provided: I used the Binomial Theorem to expand (k+1)^7, and 
because 7 is a prime, all the intermediate terms are divisible by 7; 
this is because

(n+1)^p = C[p,0]n^p + C[p,1]n^(p-1) + C[p,2]n^(p-2) + ... + C[p,p]n^0,

where C[p,m] is the binomial coefficient, p!/(m!(p-m)!). And because p 
is prime, for m = 1, 2, ... p-1, the numerator contains the factor p, 
but the denominator never does; hence C[p,m] is divisible by p for 
each of these m. Therefore the proof can be extended to prime numbers; 
I leave this to you as an excercise.

There is a very short proof using congruences, but I'll leave it to 
you to research and discuss it.  It is a much more powerful and 
elegant proof than induction, and it generalizes quite well.

- Doctor Pete, The Math Forum
  http://mathforum.org/dr.math/