Theorem 1.
For integers (x,y,p) = 1 and p prime,
1. x^(p-1) - y^(p-1) is divisible by p.
Proof 0.
Clearly, BY Fermat's Little Theorem we know (x^(p-1) - 1) and
(y^(p-1) - 1) are divisible by p. Then their difference,
(x^(p-1) - 1) - (y^(p-1) - 1) = x^(p-1) - y^(p-1) is divisible
by p. This is the arguement we want to avoid.
Proof 1.
Use the binomial expansions of (x+1)^p and (y+1)^p. This is the way
I attempted to prove this when I discovered it in the 60's.
Fermat's Last Theorem prompted me to look at x^3 +/- y^3 is
divisible by 7. playing with this, I noticed that for odd p,
x^(p-1)/2 +/- y^(p-1)/2 is divisible by p. Obviously, multiplying
these parities give the result of 1.
We can use the binomial theorem and mathematical induction to prove
x^p-x is div p and y^p-y is divisible by p.
For x=y=1
1^p-1 = 0 is div by p so the statement is true for x=1,y=1.
Induction hypotheses: x^p - x is div by p and y^p - y is div by p.
By expanding (x+1)^p and (y+1)^p we have
(x+1)^p = x^p+ph+1 for some integer h
(y+1)^p = y^p+ph1+1 for some integer h1
Then
(x+1)^p - x^p-1 = ph
(y+1)^p - y^p-1 = ph1
Adding x^p-x and y^p-y to the above two equations we have,
2. (x+1)^p-(x+1) = ph+x^p-x
3. (y+1)^p-(y+1) = ph1+y^p-y
Clearly, since x+1 and y+1 divide the left sides of 2.and 3.,they
divide the right sides of 2. and 3. Therefore, after dividing by
x+1 and y+1 we have,
4. (x+1)^(p-1)-1 = (ph+x^p-x)/(x+1)
5. (y+1)^(p-1)-1 = (ph1+y^p-y)/(y+1)
Subtracting 5. from 4. we get
(x+1)^(p-1)-(y+1)^(p-1) = (ph+x^p-x)/(x+1)-(ph1+x^p-y)/(y+1)
Now by the induction hypothesis, x^p-x = x^(p-1)-1 is divisible by p
and y^p-y = y^(p-1)-1 is divisible by p. So
(ph+x^p-x)/(x+1)-(ph1+x^p-y)/(y+1) is divisible by p.If x+1 = pk for
some k and y+1 = pk1 for some k1, p still divides. And so, we have
shown by the induction hypothesis (x+1)^(p-1) - (y+1)^(p-1) is
divisible by p.Therefore, the statement x^(p-1)-y^(p-1) is divisible
by p is true for all x and y, (x,y,p) = 1.
So we have the following special case of Theorem 1.
If y = 1 in 1., x^(p-1) - 1 is div by p (Fermat's Little Theorem)
If we relax the condition to not use Euler's Theorem,
Proof 2.
Definition: phi(p) = number of positive integers, not exceeding
p and coprime to p.
Euler's Theorem: gcd(a,p) = 1 implies a^phi(p)-1 is div by p.
From Euler's theorem, we transform 1. to
2.1 (x^phi(p)-1)-(y^phi(p)-1) = x^phi(p)-y^phi(p) is div by p.
Since all positive integers less than prime p are coprime to p,
phi(p) = p-1. Then 2.1 becomes
x^(p-1)-y^(p-1) is div by p as desired.
Again we have the following special case to Theorem 1.
If y = 1 in 1., x^(p-1)-1 is div by p (Fermat's Little Theorem)
It is surprising that it took until Euler to first publish a proof
of this special case.
Proof 3.
Lemma 1. (k,p) = 1 and s,t such that sk = tk mod p then
s = t mod p.
Proof of Lemma 1.
(s-t)k = 0 mod p. Since (k,p) = 1 it follows p divides s-t which
implies s = t mod p.
Let X be the set of non-zero residues 1x,2x,3x,...(p-1)x mod p.
By Lemma 1, p does not divide ix for all i < p-1 in X. Also, p
does not divide any of the non-zero residues X'= 1,2,3,...p-1.
and the set X is congruent to the set X' in some order. Multiplying
the elements in these sets we have 1x*2x*3x*...*(p-1)x =
1*2*3...*(p-1) mod p or rearranging we get
3.1 (p-1)!x^(p-1) = (p-1)! mod p
Similarly,
Let Y be the set of non-zero residues 1y,2y,3y,...(p-1)y mod p.
By Lemma 1,p does not divide iy for all i < p-1 in Y. Also, p does
not divide any of the non-zero residues Y'= 1,2,3,...p-1. and the
set Y is congruent to the set Y' in some order. Multiplying the
elements in these sets we have 1x*2x*3x*...*(p-1)x = 1*2*3...*(p-1)
mod p or rearranging,
3.2 (p-1)!y^(p-1) = (p-1)! mod p
Subtracting 3.2 from 3.1 we have (p-1)!(x^(p-1) - y^(p-1)) = 0 mod p.
Since p does not divide (p-1)! p divides x^(p-1) - y^(p-1) as desired.
Ref.
1 Topics from the theory of numbers by Emil Grosswald 1966, pp 43-44.
2 Elementary number theory by Garath A Jones and J Mary Jones p 68.
http://www.fact-index.com/p/pr/proofs_of_fermat_s_little_theorem.html#A%20direct%20proof
Cino Hilliard
