# Combining results with Chinese Remainder Theorem?

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

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

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.

• 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$. Mar 18 '14 at 0:55
• 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}$$ Mar 18 '14 at 1:52
• @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. Mar 18 '14 at 3:16
• @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. Mar 18 '14 at 3:19