# Math Help - Quadratic Congruence

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

Here's what I have so far:
[If] Assume that ax^2 + bx + c = 0 (mod p) is solvable.
Since p is an odd prime, gdp(4a, p) = 1. So the quadratic congruence is equivalent to 4a(ax^2 + bx + c) = 0 (mop p). 4a(ax^2 + bx + c) = (2ax + b)^2 - (b^2 - 4ac), so (2ax + b)^2 = (b^2 - 4ac) (mod p). Let y = (2ax + b) and d = (b^2 - 4ac), so y^2 = d (mod p).
If (2ax + b)^2 = (b^2 - 4ac) (mod p) has a solution, (b^2 - 4ac) is a quadratic residue of p. Does this make any sense?
Now, I don't know how to show that (b^2 - 4ac) can also be zero.

[Only If] Assume that (b^2 - 4ac) is either 0 or a quadratic residue of p.
For this proof, I don't even know how to start it. I was thinking about using Euler's criterion, so (b^2 - 4ac)^((p - 1)/2) = 1 (mod p), but I'm not sure if gcd((b^2 - 4ac), p) = 1 or not and I'm not sure if this is the right way to go, and if it is, how to proceed further. And what do I do with (b^2 - 4ac) = 0?

Any form of help if greatly appreceated.

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

Here's what I have so far:
[If] Assume that ax^2 + bx + c = 0 (mod p) is solvable.
Since p is an odd prime, gdp(4a, p) = 1. So the quadratic congruence is equivalent to 4a(ax^2 + bx + c) = 0 (mop p). 4a(ax^2 + bx + c) = (2ax + b)^2 - (b^2 - 4ac), so (2ax + b)^2 = (b^2 - 4ac) (mod p). Let y = (2ax + b) and d = (b^2 - 4ac), so y^2 = d (mod p).
If (2ax + b)^2 = (b^2 - 4ac) (mod p) has a solution, (b^2 - 4ac) is a quadratic residue of p. Does this make any sense?
Now, I don't know how to show that (b^2 - 4ac) can also be zero.

[Only If] Assume that (b^2 - 4ac) is either 0 or a quadratic residue of p.
For this proof, I don't even know how to start it. I was thinking about using Euler's criterion, so (b^2 - 4ac)^((p - 1)/2) = 1 (mod p), but I'm not sure if gcd((b^2 - 4ac), p) = 1 or not and I'm not sure if this is the right way to go, and if it is, how to proceed further. And what do I do with (b^2 - 4ac) = 0?

Any form of help if greatly appreceated.

Much simpler, in my opinion: since $(a,p)=1\,,\,\,a$ is invertible in $\mathbb{F}_p:=\mathbb{Z}\slash\mathbb{Z}_p$ and thus you can freely use the well-known high-schoolish formula to find

the zeroes of a quadratic equation: $x_{1,2}=\frac{-b\pm \sqrt{\Delta}}{2a}\,,\,\,\Delta=b^2-4ac$ ...UNLESS $p=2$ , but then $ax^2+bx+c=x^2+bx+c$ , and this can simply be solved (or not) by direct inspection.

Tonio

3. Originally Posted by tonio
Much simpler, in my opinion: since $(a,p)=1\,,\,\,a$ is invertible in $\mathbb{F}_p:=\mathbb{Z}\slash\mathbb{Z}_p$ and thus you can freely use the well-known high-schoolish formula to find

the zeroes of a quadratic equation: $x_{1,2}=\frac{-b\pm \sqrt{\Delta}}{2a}\,,\,\,\Delta=b^2-4ac$ ...UNLESS $p=2$ , but then $ax^2+bx+c=x^2+bx+c$ , and this can simply be solved (or not) by direct inspection.

Tonio
I realize that b^2 - 4ac is taken from the quadratic equation, but this is a congruence -- it works well with addtion and multiplication, but division and taking the square root can't be done, and cancellation of a
common factor on both sides of a congruence can only be done
in proper circumstances. Right? (This is something I got from my notes, my textbook and from what my prof said.)

Thanks

4. Originally Posted by firicle
I realize that b^2 - 4ac is taken from the quadratic equation, but this is a congruence -- it works well with addtion and multiplication, but division and taking the square root can't be done, and cancellation of a
common factor on both sides of a congruence can only be done
in proper circumstances.

EVERYTHING in this world can be done ONLY in proper circumstances...

What your congruence modulo p says is that the quadratic equals zero in $\mathbb{F}_p$ and thus you can freely use the given formula.

And all the arithmetic operations , up to and including roots, can be done modulo p "under the proper circumstances" (for example, never dividing by zero...)

Tonio

Right? (This is something I got from my notes, my textbook and from what my prof said.)

Thanks
.