Combining results with Chinese Remainder Theorem?

Question

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

Answer 1

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.