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$.
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
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$.