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

1. Jan 29, 2012

SpiffyEh

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?

2. Jan 30, 2012

SpiffyEh

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

3. Jan 31, 2012

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 1k=1 for all k.