-1
$\begingroup$

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$.

$\endgroup$
  • $\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
2
$\begingroup$

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$.

| improve this answer | |
$\endgroup$

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