Prove the following theorem:
Suppose $p$ is a prime number, $r$ and $s$ are positive integers and $x$ is an arbitrary integer.
Then we have $x^r \equiv x^s\bmod p$ whenever $r \equiv s \bmod (p-1)$.
Prove the following theorem:
Suppose $p$ is a prime number, $r$ and $s$ are positive integers and $x$ is an arbitrary integer.
Then we have $x^r \equiv x^s\bmod p$ whenever $r \equiv s \bmod (p-1)$.
Let $r-s=k(p-1)$ where k is a non-negative integer (assume wlog that r>=s) Using Fermat's little theorem we know that $x^{p-1}=1$ (mod $p$) therefore $x^{k(p-1)}=1$ (mod $p$).
Thus, $x^{r-s}=1$ (mod p). Now multiply by $x^s$ to get: $x^r=x^s$ (mod p)