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

## 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?

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

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.