Quadratic congruence equation with even modulus

Question

I've been thinking for a while about how to go about solving the equation $x^2+3x+8 \equiv 0 \pmod{144}$ and similar ones. When the modulus is odd it's not too tricky, but when it is I can't see quite how to find all solutions. I tried solving $x^2+3x+8 \equiv 0 \pmod{9}$ ($x=2$ or 4) and $x^2+3x+8\equiv 0 \pmod{16}$ ($x=5$ or 8) and then using the CRT to find the solutions, $x=40, 56, 85, 101$, which also solve the original equation. Brute forcing shows that there are no more solutions, but this method seems suboptimal. Is there a systematic way to solve this type of equation?

Edit: Apparently I made a mistake. Solving the equation in mod 16 and 27 on their own and then using the CRT gives all 4 solutions. However, I would still be interested to know if there is a better way! (for instance, now I solved $x^2+3x+8 \equiv 0 \pmod{16}$ by force, which isn't too difficult but seems unneccesary).

Answer 1

Well, the most "straight-forward" method I can see other than via the CRT is to complete the square, and then use modular arithmetic where necessary. This gives

$$ (x+3/2)^2-9/4+8 \equiv 0 $$

Division by two isn't possible mod 144 directly, so we multiply everything by 4, including the mod value.

$$ (2x+3)^2+23 \equiv 0 \mod 576\\(2x+3)^2 \equiv 553 $$ As it happens, $553 \equiv 83^2 \mod 576$. So one solution is found by taking the square root,

$$ 2x+3 \equiv \pm 83 \mod 576 $$ So we have $2x\equiv 80$ and $2x\equiv -86$. Dividing through by 2 (including the mod itself) gives

$$ x \equiv 40\textrm{ or }-43 \mod 288 $$ Of course, we want it mod 144, so we can simply lower the mod down one. This gives $x\equiv 40$ and $x \equiv 101$. Similarly, $553 \equiv 115^2 \mod 576$, which, by the same reasoning, will give us $x\equiv 56$ and $x\equiv 85$.

This is, of course, a much more long-winded way to do it than using the CRT. I would think the CRT would be the most natural way to do it.

Answer 2

Hint:

$x^2+3x \equiv 1 \mod 9$, $x(x+3) \equiv \mod 9 \implies x \equiv 2$ 0r $4 \mod9$

$x^2+3x \equiv 8 \mod 16$, $x(x+3) \equiv \mod 16 \implies x\equiv 5$ or $8 \mod 16$

Answer 3

If CRT seems "suboptimal" then you are probably missing some optimizations, since in this case CRT is so simple that it can be done mentally. If $\rm\ x \equiv a\,\ (mod\ 9),\,\ x\equiv b\,\ (mod\ 16),\:$ then $\rm\: x = b + 16n,\:$ so $\rm\: mod\ 9\!:\ a\equiv x\equiv b+16n\equiv b-2n\:\Rightarrow\: n\equiv (b-a)/2.\:$ Therefore

$$\rm\ x \,\equiv\, b+16\,n\,\equiv\, b + 16\left[\dfrac{b-a}{2}\ mod\ 9\right]\ \ (mod\ 9\cdot 16)$$

Thus $\rm\: a,b\,\equiv\, 4_9,8_{16}\to\ 8+16[(8\!-\!4)/2\ mod\ 9] \equiv 8+ 16(2)\equiv 40_{144}$

and $\rm\,\ \ a,b\,\equiv\, 4_9,5_{16}\to\ 8+16[(5\!-\!4)/2\ mod\ 9] \equiv 5+ 16(10/2\ mod\ 9)\equiv 85_{144}$

Remark $\ $ The computation is easy since it is trivial to compute $\rm\:k/2\:$ modulo odd $\rm\,m.\,$ Namely if $\rm\: k = 2j\:$ is even then $\rm\:k/2 \equiv 2j/j \equiv j.\:$ Else $\rm\:k\:$ is odd, and we can reduce to the even numerator case by adding $\rm\:m\:$ to the numerator, i.e. $\rm\: k/2 \equiv (k\!+\!m)/2,\:$ where $\rm\:k,m\:$ odd $\rm\Rightarrow\,k\!+\!m\,$ even. For example, above we employed this: $\rm\ \ mod\ 9\!:\ \ 1/2\equiv (1\!+\!9)/2\equiv 5.$