In a book im reading the following definition is given for a primitive root:

"An integer $a$ is called a primitive root mod $p$ if $\overline{ a }$ generates the group $U(\mathbb{Z}/p\mathbb{Z})$. Equivalently, $a$ is a primitive root mod $p$ if $p-1$ is the smallest positive integer such that $a^{p-1} \equiv 1 \text{ mod } p$."

I'm having a lot of trouble understanding why these two definitions are equivilant. Would anybody be able to explain why?

  • $\begingroup$ Do you know how many elements $U(ℤ/pℤ)$ has? $\endgroup$ – k.stm Jan 30 '18 at 14:33

Assuming $p$ is a prime, the group $U(\Bbb Z/p\Bbb Z)$ has prder $p-1$. So if the group is cyclic and has a generator $a$ (it is, and does, but that's a different theorem), then $a$ must necessarily have order $p-1$. Conversely, if there is an element $a$ of order $p-1$, it must necessarily generate the whole group.

  • $\begingroup$ I see, so if $a$ is a primitive root (according to the second definition), then it must necessarily have order $p-1$ in $U(\mathbb{Z}/p\mathbb{Z})$. Therefore, it is a generator of $U(\mathbb{Z}/p\mathbb{Z})$. And the other way round, if $a$ is a generator of $U(\mathbb{Z}/p\mathbb{Z})$, then it must have order $p-1$, which gives us that $a^{p-1} \equiv 1 \text{ mod } p$. Is this the right way of thinking about it? $\endgroup$ – xyz-x Jan 30 '18 at 14:40
  • $\begingroup$ @xyz-x I don't know if it is the right way of thinking about it. There are often many ways to think about the same thing. But from what I can read in your comment it seems like a good way, and more or less what I had in mind. $\endgroup$ – Arthur Jan 30 '18 at 14:42

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.