I know how to prove this the other way, but I don't see how the if and only if statement works in this direction. One thought I had was to try to show that the exponent was even as I know that this is the only way for $a$ to be a quadratic residue. I'm not really sure how to go about doing this though.

  • $\begingroup$ The exponent will only be even if $p \equiv 1 \pmod{4}$, and that doesn't have to happen. You still need to handle the case $p \equiv 3 \pmod{4}$. $\endgroup$ – Robert Shore Mar 21 at 1:32
  • $\begingroup$ When $\ a^{(p-1)/2}\equiv 1 \pmod{p}\ $ the Tonelli-Shanks algorithm enables you to calculate the $\hspace{-0.2em}\pmod{p}\ $ square-root of $\ a\ $ explicitly. See the Wikipedia article at: en.wikipedia.org/wiki/Tonelli–Shanks_algorithm $\endgroup$ – lonza leggiera Mar 22 at 2:12

If $a$ is a quadratic residue, there exists $x$ such that $$x^2\equiv a\pmod p$$

$$a^{(p-1)/2}\equiv x^{p-1}\equiv?\pmod p$$

Alternatively $g$ is a primitive root, $$(g^k)^{(p-1)}\equiv1\pmod p$$ will hold true iff $p-1$ divides $k(p-1)/2\iff2|k$

If $k=2m$ $$g^{2m}\equiv(g^m)^2\pmod p$$

  • $\begingroup$ yes I know by Fermat's Little Theorem that this then is equal to 1. It is proving the other side of the if and only if statement where I am a little confused $\endgroup$ – joseph Mar 21 at 2:11
  • 1
    $\begingroup$ @josephF, Conversely if $x^2\equiv a,a^{(p-1)/2}\equiv -1,$ $$-1\equiv a^{(p-1)/2}\equiv x^{p-1}\equiv1$$ $\endgroup$ – lab bhattacharjee Mar 21 at 2:28

The homomorphism $\phi: (\Bbb Z/p \Bbb Z)^* \to (\Bbb Z/ p \Bbb Z)^*$ defined by $\phi(x) = x^2$ has kernel $\{1, -1 \}$, so $|\operatorname{image}(\phi)|= \frac{p-1}{2}.$ Since $(\Bbb Z / p \Bbb Z)^*$ has $\frac{p-1}{2}$ elements satisfying $x^{\frac{p-1}{2}}=1$, $a$ must be in the image of $\phi$.


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.