• May 11th 2009, 01:39 PM
cathwelch
$\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