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

### 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,

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/

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