Proof of number being a primitive root

Question

Question: let $p$ be a prime and let $g, k$ be integers. Show that if $g^k$ is a primitive root for $p$, then $g$ is a primitive root for $p$.

My attempt: given that $g^k$ is a primitive root for $p$, then:

${(g^k)}^{p-1} \equiv 1 \bmod p$

${(g^{p-1})}^{k} \equiv 1 \bmod p$

${(g^{p-1})}^{k} \equiv g^{p-1} * g^{p-1} * \dots * g^{p-1} \equiv 1 \bmod p$

Using Fermat's little theorem: $g^{p-1} \equiv 1 \bmod p$ because $p \in \mathit{PRIMES}$ and $\gcd(p-1, p) = 1$

Therefore: ${(g^{p-1})}^{k} \equiv 1 \bmod p$

and $g^{p-1} \equiv 1 \bmod p$ $ \leftarrow$ not true yet. To complete the proof, we need to show $g^i \not\equiv 1 \bmod p$ for $1 \le i < p-1$. But my question is how to prove this last part?

Answer 1

Since $g^k$ is a primitive root mod $p$, we know that the powers of $g^k$ achieve equivalence with all values coprime to $p$ (before reaching $(g^k)^{p-1} \equiv 1 \bmod p$).

However this means that all the residue classes coprime to $p$ can also be expressed as powers of $g$ - that is, $g^k, g^{2k}, g^{3k} $ etc.. Therefore $g$ must also have order $p\!-\!1$ and is a primitive root.

Answer 2

Method$\#1:$

We know, ord$_ma=d,$ ord$_m(a^k)=\dfrac d{(d,k)}$ (Proof @Page#$95$)

Now if ord$_pg=d$ where $1<d\le p-1$

$\implies \dfrac d{(d,k)}\le d\le p-1$ the first equality occurs if $(d,k)=1$

Now we have ord$_p(g^k)=p-1$ which is only possible if $d=p-1,(d,k)=1$

Method$\#2:$

Let $h$ is a primitive root $\pmod p$ and $g\equiv k^a\pmod p\implies g^k\equiv h^{ak}$

As ord$_ph=$ord$_p(g^k)=\phi(p)=p-1,$ we need $$p-1=\dfrac{p-1}{(p-1,ak)}\implies(p-1,ak)=1$$

$\implies(p-1,a)=1\implies$ord$_pg=\dfrac{p-1}{(p-1,a)}=?$

Answer 3

Your argument doesn't help much in proving $g$ is primitive root modulo $p$. It's obvious that $(g^k)^{p-1}=(g^{p-1})^k \equiv 1 \pmod{p}$ even if $g^k$ is not primitive root modulo $p$.

Since it's obvious that $g^{p-1} \equiv 1 \pmod{p}$ for all $\gcd (g,p)=1$ so it suffices to prove $g^i \not\equiv 1 \pmod{p}$ for all $1 \le i \le p-2$. Since $g^k$ is primitive root modulo $p$ so $\gcd (k,p-1)=1$, otherwise if $\gcd (k,p-1)=r>1$ then $(g^k)^{(p-1)/r} \equiv 1 \pmod{p}$, a contradiction.

From $\gcd(k,p-1)=1$ we find $\{ki \; | \; 1 \le i \le p-2 \} \cup \{ 0\}$ is a complete residue system modulo $p-1$. That means for each $1 \le i \le p-2$ then $(g^k)^i=g^{ki} \equiv g^l \pmod{p}$ for some $1 \le l \le p-2$. We know $(g^k)^i \not\equiv 1 \pmod{p}$ so $g^l \not\equiv 1 \pmod{p}$ for $1 \le l \le p-2$. This claim gives that $g$ is primitive root modulo $p$.

Answer 4

We know (from Gauss) that each element of $1,\dots,p-1$ belongs to a divisor $d$ of $p-1$, and there are $\phi(d)$ of each element with order $d$, where $\phi$ is the Euler Totient function.

So for a prime $p$, then are $\phi(p-1)=k$ primitive roots.

If $b$ is one such primitive root, and the integers coprime to $p-1$ are say $c_1,\dots,c_k$, then the primitive roots of $p$ are given by:

$$b^{c_1},\dots,b^{c_k}$$

If $\gcd(p,q)=1$, then $qc_1,\dots,qc_k$, taken $\pmod p$, are all distinct and coprime to $p$.

So if we raise each of $b^{c_1},\dots,b^{c_k}$ to the power $q$ we get:

$$b^{qc_1},\dots,b^{qc_k}$$

which is a permutation of the original sequence.

As $b^n$, for some $n\not\mid p-1$, is a primitive root, therefore so is $b$, because for some $q$ coprime to $p$, $qn\equiv 1\pmod p-1$.