Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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!
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$.
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 $$
