Let p be an odd prime with $(a,p) = 1$ and $(\frac{a}{p})$ = 1. show that $x^2$ ≡ a (mod p) has precisely two incongruent solutions mod p.
- Having a bit of trouble with this question, we are currently covering a section on quadratic reciprocity and didn't really see anything in my notes that helped me solve this. Any help is greatly appreciated.
To me the condition $(a/p)=1$ includes $(a,p)=1$.
Saying that $(a/p)=1$ says that $a$ is a quadratic residue of $p$.
So by definition if $(a/p)=1$ then the congruence $x^2\equiv a\pmod{p}$ has at least one solution, say $b$. We will show that it has exactly two solutions.
First note that if $b^2\equiv a\pmod{p}$, then $(-b)^2\equiv a\pmod{p}$. Note also that if $p$ is odd, then $b\not\equiv -b\pmod{p}$. So if $(a/p)=1$ then the congruence $x^2\equiv a \pmod{p}$ has at least two solutions. It remains to show there are no more than two.
If $b$ is a solution, and $x$ is any solution, then $x^2\equiv a\pmod{p}$ and $b^2\equiv a\pmod{p}$, and therefore $x^2\equiv b^2\pmod{p}$.
Thus $(x-b)(x+b)\equiv 0\pmod{p}$. So $p$ divides the product $(x-b)(x+b)$, and therefore $p$ must divide one of the terms (Euclid's Lemma). It follows that $x\equiv b\pmod{p}$ or $x\equiv -b\pmod{p}$, so there are only two solutions.