1. ## Quadratic Reciprocity/ Euler's Criterion

Question:
Let p be an odd prime and gcd(a,p)=1. Establish that the quadratic congruence ax^2+bx+c = 0(modp) is solvable if and only if b^2-4ac is either zero or a quadratic residue of p.

2. $\displaystyle ax^2 + bx + c \equiv 0\left( {\bmod .p} \right)$ if and only if (multiple by 4a): $\displaystyle 4a^2 x^2 + 4abx + 4ac \equiv 0\left( {\bmod .p} \right)$ -the 'if and only if' is true since (4a, p)=1 - or equivalently: $\displaystyle \left( {2ax + b} \right)^2 + 4ac \equiv b^2 \left( {\bmod .p} \right)$ that is $\displaystyle \left( {2ax + b} \right)^2 \equiv b^2 -4ac\left( {\bmod .p} \right)$(1)

From here it is obvious that $\displaystyle ax^2 + bx + c \equiv 0\left( {\bmod .p} \right)$ implies either $\displaystyle p|(b^2 - 4ac)$ or $\displaystyle \left( {\tfrac{{b^2 - 4ac}} {p}} \right) = 1$

Conversely if either $\displaystyle p|(b^2 - 4ac)$ or $\displaystyle \left( {\tfrac{{b^2 - 4ac}} {p}} \right) = 1$ we can see that our congruence is solvable as follows:

1. If $\displaystyle p|(b^2 - 4ac)$ our congruence ( remember (1) ) holds if $\displaystyle \left( {2ax + b} \right)^2 \equiv 0\left( {\bmod .p} \right)$ now $\displaystyle 2ax\equiv{-b}(\bmod.p)$ is solvable since (2a, p)=1. Thus our congruence is solvable.

2. If $\displaystyle \left( {\tfrac{{b^2 - 4ac}} {p}} \right) = 1$ we have $\displaystyle b^2 - 4ac \equiv y^2 \left( {\bmod .p} \right)$ for some $\displaystyle 0<y<p$ and it is enough to take: $\displaystyle 2ax + b \equiv y\left( {\bmod .p} \right)$ which is solvable since (2a, p)=1