Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
    
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$....) – Greg Martin Apr 11 '14 at 2:05
    
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)). – Tom Dwan Apr 11 '14 at 6:30
    
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. – Tom Dwan Apr 11 '14 at 6:30
    
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! – Greg Martin Apr 11 '14 at 6:59
1  
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$. – Greg Martin Apr 11 '14 at 8:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.