2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.. $\endgroup$ – rsadhvika Dec 8 '18 at 8:17
  • $\begingroup$ You can try David Burton's Elementary Number Theory. $\endgroup$ – Brahadeesh Dec 8 '18 at 8:25
  • $\begingroup$ Thank you, I will definetly check this one. $\endgroup$ – R. Jacks Dec 8 '18 at 8:37
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thank you! This was a big help. $\endgroup$ – R. Jacks Dec 9 '18 at 11:59
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you! Got this one explained and now I can continue with existence. $\endgroup$ – R. Jacks Dec 9 '18 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.