3
$\begingroup$

Problem
Prove that the congruence equation $ax^2 + bx + c \equiv 0 \pmod{m}$, with $(2a, m) = 1$ is equivalent to a congruence of the form $x^2 \equiv r \pmod{m}$.

I really have no idea where to start. Is there a theorem which relates to this problem? What do we have to show? A hint would be sufficient.

Thanks,

2 Answers 2

2

Multiply it by the unit $\rm\:4a\:$ yielding the equivalent equation $\rm\ (2\:a\:x+b)^2\: =\ b^2 - 4\:a\:c\ \ (mod\ m)$

1

Remember the quadratic formula to solve $ax^2 + bx + c = 0$: $x = \tfrac{1}{2a}(-b \pm \sqrt{b^2 - 4ac})$.

This works for the congruence too if we just interpret it right.

Suppose $r^2 \equiv b^2 - 4ac$ then it's easy to check that $x \equiv (2a)^{-1} (-b \pm r)$ solves the quadratic. The condition 2a coprime is m is exactly what's needed to invert 2a.

if x solves the quadratic congruence then multiply by 2a and add b to get the other direction.