1. The problem statement, all variables and given/known data 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. 2. Relevant equations I understand that fermat's little theorm is: Let p be prime, and b e Z_p. Then b^p = b (mod p). 3. 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?