- #1

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