0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Try $p = 7$, it doesn't follow. $\endgroup$ – Daniel Fischer Nov 27 '16 at 13:05
  • $\begingroup$ 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. $\endgroup$ – Shingle Nov 27 '16 at 13:12
  • $\begingroup$ 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. $\endgroup$ – Daniel Fischer Nov 27 '16 at 13:14
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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