Let $r$ be primitive root mod $p$. When $x$ goes from $1$ to $p-1$, then $r^x$ (mod $p$) goes through all the numbers $1,\dots,p-1$ in some order

Question

I'm trying to understand this situation. Why do the powers of primitive roots smaller than $p-1$ generate all DISTINCT elements in $\mathbb{Z}_p$? I am aware about what Fermat's little theorem states and about the fact that $\mathbb{Z}_p$ has $p-1$ elements in it. Just not sure how to prove that those elements are distinct and I'm having a struggle with finding proper texts about this.

Answer 1

Suppose $r^a\equiv r^b \pmod p $ for some $1\leq a,b\leq p-1$ . Since $(r^b,p)=1$,inverse of $r^b$ exists, say, $r^{-b}$. Multiplying the first equation by $r^{-b}$ will give us $r^{a-b}\equiv 1 \pmod p $. Since $r $ is a primitive root and $1\leq a,b\leq p-1$, the only possibility is $a=b $. Hence, $r^x \pmod p$ produces distinct elements as $x$ varies from $1$ to $p-1$. Since there are $p-1$ distinct elements, these elements corresponds the elements of the set $\{1,2,\ldots,p-1\} $.

Answer 2

We have a group of order $p-1$ (the non-zero class mod $p$ under multiplication) and by definition a primitive root is an element of order $p-1$, so $x^{p-1} =1$ and $x^n \neq 1$ for all $1 \le n < p-1$ ($p-1$ is the minimal power that gives $1$). Distinctness is then simpel group theory:

If $x^r = x^s$ for some $1\le s < r < p-1$ then $x^r\cdot (x^s)^{-1} = x^{(r-s)}=1$ and as $1 \le r-s < p-1$ this contradicts the minimality condition of the order. So all $x^r$ are distinct for $1 \le r < p-1$.