Fermat's Little Theorem: A Special CaseDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/