1
$\begingroup$

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

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I guess the CRT would be the easiest way, but yours was enlightening as well. Thank you! $\endgroup$
    – maestron
    Mar 22, 2013 at 14:11
0
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ I'm not sure I see your point. Are you hinting at some better way to solve x^2+3x=8 mod 16 than by inspection? $\endgroup$
    – maestron
    Mar 22, 2013 at 14:08
  • $\begingroup$ There is, although it's not really made clear by the answer given. Because it's equivalent to 8, and the two factors are of opposite parity, you know that one of them must be equal to 8. Therefore, either x=8 or x+3=8 -> x=5. $\endgroup$
    – Glen O
    Mar 22, 2013 at 14:41
  • $\begingroup$ The same approach can be taken for the mod 9 case, although the factorisation isn't currently right - it should be (x+1)(x+2)=3, rather than x(x+3)=1. From that, you know that one factor must be either 3 or 6. The other factor must be whichever one will result in the product being 3 rather than 6. 2*3 = 6, 3*4=3, 5*6=3, 6*7=6. So x+1=3 or x+1=5, giving x=2 or 4. $\endgroup$
    – Glen O
    Mar 22, 2013 at 14:44
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .