Let $p$ denote an odd prime and let $a\in\mathbb{Z}$ with $\gcd(a,p)=1$. I want to show that it holds $$\exists x\in\mathbb{Z}:x^2\equiv a\text{ mod }p\;\;\;\Leftrightarrow\;\;\;a^\frac{p-1}{2}\equiv 1\text{ mod }p$$

Proof: Since $p$ is prime and $p\nmid a$, it follows from Fermat's little theorem: $$\left(a^\frac{p-1}{2}-1\right)\left(a^\frac{p-1}{2}+1\right)=a^{p-1}-1\equiv0\text{ mod }p$$ But (again) since $p$ is prime, one of the factors on the left side must be multiples of $p$, i.e. $$a^\frac{p-1}{2}\equiv\pm 1\text{ mod }p$$ Now I would like to prove the equivalence. Let's start with the direction "$\Rightarrow$". How do I need to argue here?

PS: I'm not sure where exactly I need that $p$ is uneven, i.e. $p\ne 2$.

  • $\begingroup$ If $p$ is even then $a^{\frac{p-1}{2}}=a^{\frac{1}{2}}$ which might not be an integer. $\endgroup$ – Rocket Man Jun 9 '14 at 12:21
  • $\begingroup$ Hint: The multiplicative group modulo $p$ is cyclic of order $p-1$. $\endgroup$ – Hagen von Eitzen Jun 9 '14 at 12:23

One direction is easy if $x^2\equiv a \pmod p$ then taking both sider to power $\frac{p-1}{2}$ we have

$$x^{p-1}\equiv a^{\frac{p-1}{2}} \pmod p$$

but $$x^{p-1}\equiv 1\pmod p$$ so $$a^{\frac{p-1}{2}} \equiv 1\pmod p$$

The other direction is based on the fact that there is a primitive root modulo $p$, a number $g$ such that $g^{p-1}\equiv 1 \pmod p$ and for no smaller power $n < p-1$ is $g^{n}\equiv 1 \pmod p$. If $a\equiv g^k \pmod p$ then $$a^{\frac{p-1}{2}} \equiv g^{k\frac{p-1}{2}}\pmod p$$

so $$ g^{k\frac{p-1}{2}}\equiv 1\pmod p$$ which means that $p-1|k\frac{p-1}{2}$ and this can only happen if $k$ is even, $k=2l$ so let $x=g^l$ and then

$$x^2\equiv a \pmod p$$


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.