Proving X^(k*p-1)+1)mod p = x mod p

[SpiffyEh]

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?

 

[SpiffyEh]

Can anyone help with this? I really need to understand how it works

 

[Joffan]

It sounds like you don't really understand induction. The basic idea is that you prove two things, for some statement S depending on a number:

• S(1) is true
• If S(k) is true, so is S(k+1).

And then this is taken - by induction - to prove that S(n) is true for all n, the truth "inheriting" through to all numbers.

The alternative statement of Fermat's Little Theorem in the middle of the proof there, that a^{p-1}\equiv1 \text{ mod }p, can be used to eliminate the need for induction. Then it's just a matter of knowing that 1^k=1 for all k.