prove that $\zeta^{i}$ is a primitive root modulo p $\iff$ $\gcd(p-1,i) =1$ where $p$ is prime and $\zeta$ is a primitive root modulo p.

Question

I was going to use a case by case proof, but i am relativley new to primitive roots and I couldnt see how to sufficiently prove either case.

Answer 1

Simply use the definition of a primitive root modulo $p$ :

The powers $(\zeta^i)^1,(\zeta^i)^2,\ldots,(\zeta^i)^{p-1}$ have precisely the residues $1,2,\ldots,p-1$ modulo $p$ in some order .

Now let $k=\gcd(i,p-1)$ then because $k \mid i$ :

$$(\zeta^i)^{\frac{p-1}{k}} \equiv (\zeta^{\frac{i}{k}})^{p-1} \equiv 1 \pmod{p}$$ from Fermat's little theorem .

But we already know that : $$(\zeta^i)^{p-1} \equiv 1 \pmod{p}$$ so because the powers are distinct modulo $p$ it must follow that : $$p-1=\frac{p-1}{k}$$

$$k=1$$

$$\gcd(i,p-1)=1$$

Now let's prove that $\zeta$ is also a prmitive root modulo $p$ .

Shorter way

Let $ord_p(\zeta)=l$ . We only need to prove that $l=p-1$.

$$(\zeta)^l \equiv 1 \pmod{p}$$ so :

$$(\zeta^i)^l \equiv 1 \pmod{p}$$ but $\zeta^i$ is a primitive root so it has order $p-1$ .It follows then that $p-1 \mid l$ so $l=p-1$ .

Longer way

Now because $\gcd(i,p-1)=1$ it follows that the numbers $i,2i,\ldots,(p-1)i$ are all distinct modulo $p-1$ . If for example $xi \equiv yi \pmod{p-1}$ then :

$$p-1 \mid i(x-y)$$ but $\gcd(i,p-1)=1$ :

$$p-1 \mid x-y$$ but this means that $x=y$ .

Because of this it follows that the powers $$(\zeta)^1,(\zeta)^2,\ldots,(\zeta)^{p-1}$$ are equivalent modulo $p$ with the powers : $$(\zeta^i)^1,(\zeta^i)^2,\ldots,(\zeta^i)^{p-1}$$ which are in turn equivalent modulo $p$ (because $(\zeta)^i$ is a primitive root ) with :

$$1,2,\ldots,p-1$$

But this means that $\zeta$ is also a primitive root modulo $p$, as wanted .