• May 11th 2009, 01:39 PM
cathwelch
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.
• May 11th 2009, 02:52 PM
PaulRS
$
ax^2 + bx + c \equiv 0\left( {\bmod .p} \right)
$
if and only if (multiple by 4a): $
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: $
\left( {2ax + b} \right)^2 + 4ac \equiv b^2 \left( {\bmod .p} \right)
$
that is $
\left( {2ax + b} \right)^2 \equiv b^2 -4ac\left( {\bmod .p} \right)
$
(1)

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

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

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

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