Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
Great hint! Thank you. –  Chan Apr 2 '11 at 7:27

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.

share|improve this answer
    
Many thanks. –  Chan Apr 1 '11 at 6:20
    
That only works for one direction of the equivalence. –  Bill Dubuque Apr 1 '11 at 6:26
    
It works for both ways. –  quanta Apr 1 '11 at 6:48
    
My point was that your first version did not say anything about the other direction, which, of course, is necessary to prove an equivalence. The equations are equivalent because scaling by a unit is an invertible transformation. –  Bill Dubuque Apr 1 '11 at 7:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.