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$.
Answer
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$$
No comments:
Post a Comment