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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.