4
$\begingroup$

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 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?

$\endgroup$
  • 1
    $\begingroup$ Well, there is an easy way to conclude this exercize in a line: $\Bbb{Z}_p^* = \langle g^k \rangle \subseteq \langle g \rangle \subseteq \Bbb{Z}_p^*$, so you have equality. Hence, $g$ generates the whole multiplicative subgroup of $\Bbb{Z}_p$, i.e. it is a primitive root. $\endgroup$ – Crostul Nov 13 '16 at 23:35
4
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is definitely the best answer here! To show a number is a primitive root, you have to show that its powers fill out all non-zero residue classes mod $p$. (That it has order $p-1$ follows automatically; this doesn't have to be checked.) As you observe (and as Crostul already observed in comments), if $g^k$ generates all non-zero residue classes, then $g$ certainly does! $\endgroup$ – tracing Dec 3 '16 at 3:35
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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)}=?$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Prove the contrapositive. If g is not a primitive root, its multiplicative order is a proper divisor of p-1. As g^k belongs to the group generated by g, by Lagrange's Theorem its order divides the order of g and so it can't be a primitive root. I admit this is NOT an answer to the question. I'm just saying if I was goin to Memphis, I wouldn't start from here. $\endgroup$ – Airymouse Dec 3 '16 at 3:58

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.