- #1
SpiffyEh
- 194
- 0
Homework Statement
Prove that x^(k(p–1)+1) mod p = x mod p for all primes p and integer k ≥ 0.
Hint: Use Fermat’s Little theorem and induction on k.
Homework Equations
I understand that fermat's little theorm is:
Let p be prime, and b e Z_p. Then b^p = b (mod p).
The Attempt at a Solution
Proof given in class:
If x is 0 mod p, then the statement is trivially true, so assume gcd(x,p) = 1
Let k = 1. We need to establish that x^(1(p–1)+1) = x mod p
Left side = x^p, and this = p mod p by FLT.
Now assume true for a given k, so that x^(k(p–1)+1) = x mod p
A variant of FLT tells you that x^(p–1) = 1 mod p when gcd(x,p) = 1, so apply that to
x^(k(p–1)+1) = x mod p
x^(k(p–1)+1) times x^(p-1) = x times 1 mod p
x^((k+1)(p–1)+1) = x mod p
I don't understand how this proves it at all. To me it just seems to get more complex at the end. Can anyone explain to me how this works?