# Showing two different definitions of a primitive root are the same

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?

• Do you know how many elements $U(ℤ/pℤ)$ has? – 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.
• 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? – xyz-x Jan 30 '18 at 14:40