0
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ If you have a root mod 13, the quadratic will factor mod 13. $\endgroup$ Apr 28, 2012 at 16:43

2 Answers 2

8
$\begingroup$

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$.

$\endgroup$
0
0
$\begingroup$

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 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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