Let there be $p\ ,q$ odd primes, such that $p=2q+1$.

Let the be $a \in Z^*_p$ so that $a \not= \pm 1(mod\ p)$. Prove that if $a$ is not a generator of $Z^*_p$ then $-a$ is a generator of $Z^*_p$.


closed as off-topic by fkraiem, e-sushi Jan 3 '17 at 16:14

  • This question does not appear to be about cryptography within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Please indicate what you tried and where you are stuck. $\endgroup$ – Maarten Bodewes Jan 3 '17 at 8:40
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it is about general mathematics. $\endgroup$ – fkraiem Jan 3 '17 at 10:47

Since $p$ is prime, the order of $(\mathbb Z/p)^\ast$ is $p-1=2q$, hence by Lagrange's theorem, each element must have order dividing $2q$.

Note that since $\mathbb Z/p$ is a field, there cannot be square roots of one other than $1$ and $-1$, so $a$ cannot have order $1$ or $2$. It also cannot have order $2q$ as that would make it a generator. Therefore $a$ has order $q$.

For the same reason, $-a$ cannot have order $1$ or $2$: That would imply $a$ is a square root of one. Now if $-a$ had order $q$, then $$ 1=(-a)^q=(-1)^qa^q=-a^q=-1 \text, $$ a contradiction. Therefore, we must conclude $-a$ has order $2q$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.