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.

Suppose we have $25x^2 + 70x + 37 \equiv 0 \pmod{13}$. Since it doesn't factor we obviously have to subtract/add $(ax + b)$ from both sides of the congruence. However I'm getting different answers. What is the proper way to approach solving for all residues that solve this congruence?

Thanks!

share|improve this question
    
If you have a root mod 13, the quadratic will factor mod 13. –  Mark Bennet Apr 28 '12 at 16:43
add comment

2 Answers 2

up vote 8 down vote accepted

The prime $13$ is very small. A useful strategy may be to try everything. Or not quite everything, since we know that a quadratic congruence modulo a prime has at most $2$ solutions. If we reduce our coefficients modulo $13$ to make calculations easier, we can fairly quickly find the solutions $x\equiv 8\pmod{13}$, $x\equiv 10\pmod{13}$.

Although for small primes "trial and error" is efficient, we will examine an approach through general theory. Consider the congruence $ax^2+bx+c\equiv 0\pmod{p}$, where $p$ is prime, and $a\not\equiv 0\pmod p$. Multiply through by $4a$. We get the equivalent congruence $$4a^2x^2+4abx+4ac\equiv 0\pmod{p}.$$ The purpose of multiplying through by $4a$ is to make completing the square easy. The above congruence can be rewritten as $$(2ax+b)^2-b^2+4ac\equiv 0\pmod{p},$$ or equivalently $$(2ax+b)^2\equiv b^2-4ac\pmod p.$$ Now we turn to our particular case. The supplied coefficients are largish. It is useful to note that $25\equiv -1$, $70\equiv 5$, and $37\equiv -2$, all modulo $13$. Our congruence is equivalent to $$(-2x+5)^2\equiv 17\equiv 4 \pmod{13}.$$ So we need to solve $y^2\equiv 4 \pmod{13}$, $-2x+5\equiv y \pmod{13}$.

We got a little lucky, the solutions of $y^2\equiv 4\pmod{13}$ are $y\equiv \pm2\pmod{13}$. Now solve the congruences $-2x+5\equiv 2\pmod{13}$, $-2x+5\equiv -2\pmod{13}$.

Remark: For large primes $p$, one can use exactly the same strategy to arrive at the system $y^2\equiv b^2-4ac\pmod{p}$, $2ax+b\equiv y \pmod{p}$. The only place where there is computational difficulty is in determining whether the congruence $y\equiv b^2-4ac\pmod{p}$ has a solution, and if it does, finding one.

Note also that, with suitable interpretation, what we did amounts to deriving the Quadratic Formula $x=\dfrac{-b\pm\sqrt{b^2-4ac}}{2a}$. Of course, square root has to be interpreted modulo $p$, as a solution of the congruence $y^2\equiv b^2-4ac\pmod{p}$. And division by $2a$ should be thought of as multiplication by the multiplicative inverse, modulo $p$, of $2a$.

share|improve this answer
add comment

Hint $\rm\: mod\ 13\!:\ 0 \equiv25\:x^2 + 70\:x + 37 \equiv -(x^2 -5\:x+2).\:$ Applying the quadratic formula

$$\rm x\equiv \dfrac{5\pm\sqrt{17}}2\equiv \dfrac{18\pm\sqrt{4}}2\equiv\{10,8\}\ \ \ since\ \ \ 5\equiv 18,\ 17\equiv 4 $$

share|improve this answer
add comment

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.