# Prove that if $g^{(p-1)/2} \equiv -1 (mod \mbox{ } p)$ then its smaller power can't be congruent to 1.

Let $p$ be a prime greater than $2$. Show that $g^{(p-1)/2} \equiv -1 (mod \mbox{ }p)$ implies $g^{k} \not\equiv 1 (mod \mbox{ }p)$ for every $1≤k≤(p-1)/2$.

• Try $p = 7$, it doesn't follow. – Daniel Fischer Nov 27 '16 at 13:05
• Thanks, I wasted a lot of time on thinking why I can't take g=-1 as an counterexample for p=4k+3. Seems like I fooled myself. – Shingle Nov 27 '16 at 13:12
• It's not only $p \equiv 3 \pmod{4}$, for $p = 13$, try $g = 5$. It works for Fermat primes, but those aren't very numerous. – Daniel Fischer Nov 27 '16 at 13:14

If $g^{(p-1)/2}\equiv-1\pmod p$

using Discrete Logarithm wrt primitive root $a,$

$\dfrac{p-1}2\cdot$ind$_ag\equiv$ind$(-1)\pmod{\phi(p)}$

As ind$(-1)\equiv\dfrac{p-1}2\pmod{\phi(p)}$

$\dfrac{p-1}2($ind$_ag-1)\equiv0\pmod{p-1}$

$\implies$ind$_ag$ must be odd.

Now from this, if $d|(p-1),$ there exist $\phi(d)$ values of $g$ such that ord$_pg=d$

As ind$_ag\mid(p-1),$ there will be $\phi($ind$_ag)$ values of $g$