I'll give the question, and then I'll describe the headway I've made so far.

"Let $p$ be an odd prime, and suppose that $q=2p+1$ is also prime. Prove that if $a$ is incongruent to $1$ and incongruent to $-1$ $\mod{q}$, then $(-a^2)$ is a primitive root modulo $q$."

My progress: I have shown that $q$ must be congruent to $3$ modulo $4$. Further, I've proved previously that this means that there does not exist an integer $x$ such that $x^2$ is congruent to $-1$ modulo $q$. So we have that $(-a^2)$ CANNOT be congruent to $1$ modulo $q$. From here, however, I am totally at a loss as to how to proceed.

All help appreciated. Thanks in advance.

  • $\begingroup$ The only possible orders of an element modulo $q$ are $1$, $2$, $p$, and $2p$; you're trying to show that the order of $-a^2$ is $2p$. You've already ruled out having order $1$. Can you rule out having order $2$ and having order $p$? (One of these at least must use the hypothesis $a\not\equiv\pm1\pmod q$....) $\endgroup$ – Greg Martin Apr 11 '14 at 2:05
  • $\begingroup$ Thank you Greg. I've since ruled out p, as follows: (-a^2)^p=-a^(2p) congruent to (-1) mod q. (final line is because 2p is simply phi(q)). $\endgroup$ – Tom Dwan Apr 11 '14 at 6:30
  • $\begingroup$ I can't seem to rule out 2 though. I realize this must use our assumption but I'm at a loss as to how to apply it. I'm likely missing something basic here. $\endgroup$ – Tom Dwan Apr 11 '14 at 6:30
  • $\begingroup$ Yes, but that happens sometimes :) The assumption on $a$ says that $-a^2\not\equiv-1\pmod q$, and $-1$ is the only element of order $2$ modulo a prime. Both halves of that sentence are a little nontrivial; see if you can confirm them! $\endgroup$ – Greg Martin Apr 11 '14 at 6:59
  • 1
    $\begingroup$ The math: $x$ having order dividing $m$ is equivalent to $x^m\equiv1\pmod q$. In particular, $x$ having order dividing $2$ is equivalent to $x^2-1\equiv0\pmod q$, or $(x-1)(x+1)\equiv0\pmod q$. Since $q$ is prime, either $x-1\equiv0$ or $x+1\equiv0$. (or use the fact that the number of roots of a polynomial modulo a prime is at most the degree) -- The intuition: the multiplicative group modulo $q$ is cyclic of order $q-1$. So the number of elements of order $m$ is the same as the number of elements of order $m$ in $\Bbb Z/(q-1)\Bbb Z$. When $m=2$, there's only one such element $(q-1)/2$. $\endgroup$ – Greg Martin Apr 11 '14 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.