1
$\begingroup$

Show that if $p$ is prime and $p = 2q + 1$, where $q$ is an odd prime and $a$ is a positive integer with $1 < a< p -1$, then $p - a^2$ is a primitive root modulo $p$.

I'm struggling with this one. I know the order of the primitive root has to be $2q$. I also know there are $q-1$ of them. I know $(p-a^2)^{2q} \equiv 1 \pmod{p} \Rightarrow (-a^2)^{2q} \equiv a^{4q} \equiv 1 \pmod{p}$ I know this works for all $a$ via fermats little theorem, but I dont know how to show thats actually the order. Any help or hints would be greatly appreciated

$\endgroup$
1
$\begingroup$

Let $m=2q$ be the order of the unit group modulo $p$. A unit $g$ is a primitive root if and only if $g^{m/r}\not\equiv1\pmod{p}$ for every prime divisor $r$ of $m$.

Here $r\in\{2,q\}$, so you need to have $g^q\not\equiv1\pmod{p}$, in fact $g^q\equiv-1\pmod{p}$, and $g^2\not\equiv1\pmod{p}$. The latter is easy because $p$ is prime and therefore the only solutions to $g^2\equiv 1\pmod{p}$ are $\pm1\pmod{p}$ both of which are excluded by hypothesis.

As for $g^q$ with $g = p - a^2 \equiv -a^2\pmod{p}$, we get $g^q \equiv (-a^2)^q = -a^{2q} \equiv -1\pmod{p}$, where we use the facts that $q$ is odd and that $a^m\equiv1\pmod{p}$.

$\endgroup$
1
$\begingroup$

Let $w$ be a primitive root mod $p$, i.e. a generator of the cyclic group $\mathbf F_p^*$. All the primitive roots mod $p$ are of the form $w^j$, with $j$ coprime to $p-1=2q$, with $q$ prime (by hypothesis), hence we can take $1\le j <2q, j$ odd. In particular there are exactly $q-1$ such primitive roots. It remains to characterize them in another way. Just for fun, let's proceed using quadratic residues mod $p$.

Since $\mathbf F_p^*$ is cyclic, it admits exactly one subgroup of index $2$, which is no other than the group of squares ${\mathbf F_p^*}^2$, and $\mathbf F_p^*$ is the disjoint union of ${\mathbf F_p^*}^2$ and its complement $C$, these two sets having cardinal equal to $(p-1)/2 = q$ (this means in particular that there are as many quadratic residues as non residues). Then, from what we have seen above, $C$ minus {$w^q$} is precisely the set of primitive roots mod $p$. Besides, since $(p-1)/2=q$ is odd, $-1$ is not a square, and $C=(-1){\mathbf F_p^*}^2$. This shows what we want.

$\endgroup$
  • $\begingroup$ shouldnt there be exactly $q -1$ primitive roots? since, there is the one case where $\gcd(2q, q) \neq 1$ so $w^q$ is the only odd power non primitive root? $\endgroup$ – XRBtoTheMOON Apr 11 '18 at 21:28
  • $\begingroup$ Yes, you're right, I have never been good at counting. $\endgroup$ – nguyen quang do Apr 12 '18 at 6:23
  • $\begingroup$ I edited my answer accordingly. $\endgroup$ – nguyen quang do Apr 12 '18 at 6:53

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.