4
$\begingroup$

$9x^2 + 27x + 27 \equiv 0 \pmod{21}$

What is the "correct" way to solve this using the Chinese Remainder Theorem? How do I correctly solve this modulo $3$ and modulo $7$ without brute force?

$\endgroup$
3
  • 1
    $\begingroup$ For numbers this small, you are much better off using brute force than navigating the rather complicated formulas, chock full of cases. $\endgroup$
    – vadim123
    Mar 18 '14 at 0:05
  • $\begingroup$ The congruence holds iff $3x^2+9x+9\equiv 0\pmod{7}$. $\endgroup$ Mar 18 '14 at 0:08
  • $\begingroup$ ... or even $x^2+3x+3\equiv 0\pmod{7}$. $\endgroup$
    – vadim123
    Mar 18 '14 at 0:14
1
$\begingroup$

First, modulo $3$, your congruence reduces to $0\equiv 0$, because all coefficients are multiples of $3$. Therefore there are three solutions: $x\equiv 0,1,2 (\mod 3)$.

Working modulo $7$ the congruence becomes $2x^2+6x+6\equiv 0$, or $x^2+3x+3\equiv 0$, since we can multiply both sides by the inverse of $2$. To solve this, we use the quadratic formula, noting that in our case $\frac{1}{2a}=4$. Thus $x\equiv 4(-3\pm\sqrt{9-12})\equiv 4(4\pm\sqrt{4})\equiv 4(4\pm2)\equiv 3$ or $1$.

Now, you have three solutions modulo $3$ and two solutions modulo $7$, so that's six combinations to feed into the Chinese Remainder Theorem.

$x\equiv_3 0, x\equiv_7 1 \implies x\equiv_{21} 15 \\ x\equiv_3 1, x\equiv_7 1 \implies x\equiv_{21} 1 \\ x\equiv_3 2, x\equiv_7 1 \implies x\equiv_{21} 8 \\ x\equiv_3 0, x\equiv_7 3 \implies x\equiv_{21} 3 \\ x\equiv_3 1, x\equiv_7 3 \implies x\equiv_{21} 10 \\ x\equiv_3 2, x\equiv_7 3 \implies x\equiv_{21} 17 \\$

As noted in the comments above, since the solution is everything modulo $3$, it makes more sense in this case to just solve the problem modulo $7$. However, you wanted to see the gory details, and the above method generalizes just fine.

$\endgroup$
4
  • $\begingroup$ Yeah, you can replace each coefficient with anything equivalent modulo $m$. Thus, when $m=3$, $9$ and $27$ become $0$. Dividing by the GCD is just normal algebra, possible because that GCD actually has a reciprocal modulo $m$. $\endgroup$ Mar 18 '14 at 0:55
  • $\begingroup$ CRT is overkill since, e.g. $$\,x\equiv 1\!\!\pmod 7 \iff x = 1\!+\!7k \iff x\equiv 1,\,1\!+\!7,\,1\!+\!7\!+\!7\!\!\pmod{21}$$ $\endgroup$ Mar 18 '14 at 1:52
  • $\begingroup$ @Bill_Dubuque, yeah, I tried to be clear that it was overkill, but I thought that the OP was asking for a general method. Thus, my answer. $\endgroup$ Mar 18 '14 at 3:16
  • $\begingroup$ @user135084, that's right. If you have the equation $2x+4\equiv 0 (\mod 2)$, you cannot conclude that $x+2\equiv 0 (\mod 2)$. The solution $x=2$ satisfies the former, but not the latter. $\endgroup$ Mar 18 '14 at 3:19

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.