# 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

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.

• We define primitive root of $p$ to be a number whose order is $p-1$. Then you should be asking why/how at least one primitive root exists for every prime number.. – rsadhvika Dec 8 '18 at 8:17
• You can try David Burton's Elementary Number Theory. – Brahadeesh Dec 8 '18 at 8:25
• Thank you, I will definetly check this one. – R. Jacks Dec 8 '18 at 8:37

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\}$$.
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$$.