1
$\begingroup$

How do i prove the following theorem?

Supose $p$ is a prime number, $r,\ s$ are positive integers and $x$ is an arbitary integer. Then we have $x^r \equiv x^s\ (mod\ p)$ whenever $r \equiv s \ (mod \ p-1)$.

I'm thinking of using order of powers formula:

$m^r = 1\ (mod\ n)$

and FTL:

$a^{p-1} = 1 \ (mod \ p)$

but im not sure what to do really.

2 Answers 2

4

Let $r > s$ then $x^{(r-s)} \equiv 1 \pmod p$ also $x^{(p-1)} \equiv1 \pmod p$ hence $p-1$ divides $r-s$ hence $r \equiv s (\mod (p-1))$

2

Another approach: if $\,x=0\pmod p\,$ then the claim is trivial, so let us assume

$x\neq 0\pmod p\Longrightarrow x\pmod p=:\overline x\in\left(\Bbb Z/p\Bbb Z\right)^*=:\Bbb F_p^*$

Since $\,\Bbb F_p\,$ is a finite field, $\,\Bbb F_p^*:=\Bbb F_p\setminus\{0\}\,$ is a cyclic group of order $\,p-1\,$ , thus

$x^r=x^s\pmod p\Longleftrightarrow x^{r-s}=1\pmod p\Longleftrightarrow (p-1)\mid(r-s)\Longleftrightarrow r=s\pmod{p-1}$