-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$
2
  • $\begingroup$ Please indicate what you tried and where you are stuck. $\endgroup$
    – Maarten Bodewes
    Commented Jan 3, 2017 at 8:40
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it is about general mathematics. $\endgroup$
    – fkraiem
    Commented Jan 3, 2017 at 10:47

1 Answer 1

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

$\endgroup$

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