0
$\begingroup$

Let $p$ be a prime, $g\in (\mathbb{Z}/ p\mathbb{Z})$* a primitive root.

I want to find a necessary and sufficient condition on $a\in \mathbb{Z}$ such that $g^a$ is also a primitive root.

My conjecture is that $gcd(a,p-1)=1$ is that condition. To test this, I first suppose that $gcd(a,p-1)=1$. If I get that $g^a$ is a primitive root, then my condition is sufficient. Then I suppose $gcd(a,p-1)=d$ where $d>1$ and in $\mathbb{N}$. If I get that $g^a$ is not a primitive root, then my condition is necessary.

First, I suppose $gcd(a,p-1)=1$ By the definition of a primitive root, we have $g^{p-1}\equiv 1\pmod p$ with $p-1$ the smallest integer for which the latter congruence is true. This implies $(g^{p-1})^a\equiv 1\pmod p$ and $(g^a)^{p-1}\equiv 1\pmod p$

If $p-1$ is the multiplicative order of $g^a$, we're done.

If $p-1$ is not the multiplicative order of $g^a$, then $\exists\space d\in \mathbb{N}$ such that $d|p-1$ and $\frac{p-1}{d}$ is the multiplicative order of $g^a$.

So we get $(g^a)^{\frac{p-1}{d}}\equiv 1\pmod p$ which implies $(g^{\frac{a}{d}})^{p-1}\equiv 1\pmod p$

I expected to arrive at some contradiction because $a$ and $p-1$ being coprime, it implies that $d$ does not divide $a$ but I'm not sure where the contradiction lies or if there is any. Any tips?

$\endgroup$
0
$\begingroup$

I see several mistakes there. Firstly, your argument for sufficient condition does not prove anything, both your statements about $(g^a)^{p-1}$ are true for any $a$. You want to prove $(p-1)$ is the smallest number for which that equality is true. And it is, because the smallest common multiple of $a$ and $p-1$ is $a \cdot (p-1)$, because $gcd (a,p-1)=1$.

Now, the reverse. It is similar, only now we know that the smallest common multiple of $a$ and $p-1$ is $\frac{a \cdot (p-1)}{gcd (a,p-1)}<a \cdot (p-1)$, therefore there is a number smaller than $a(p-1)$, for which we can get to $1$, because now $(g^a)^{\frac{p-1}{gcd (a,p-1)}}=1$ as well. Therefore it does not meet criteria of a primitive root.

$\endgroup$

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.