# Solve $f(x) = 6x^3 + 27x^2 + 17x + 20 \equiv 0 \pmod{30}$

Problem

Solve $f(x) = 6x^3 + 27x^2 + 17x + 20 \equiv 0 \pmod{30}$

My attempt was:

Since $30 = 2.3.5$, we then have:
$$\begin{cases} f(x) \equiv 0 \pmod{2}\\ f(x) \equiv 0 \pmod{3}\\ f(x) \equiv 0 \pmod{5}\\ \end{cases}$$

By inspection, we see that: $$\begin{cases} x \equiv 0 \pmod{2}\\ x \equiv 1 \pmod{2}\\ x \equiv 2 \pmod{3}\\ x \equiv 0 \pmod{5}\\ x \equiv 1 \pmod{5}\\ \end{cases}$$

Hence, there will be four cases:
Case 1 $$\begin{cases} x \equiv 0 \pmod{2}\\ x \equiv 2 \pmod{3}\\ x \equiv 1 \pmod{5}\\ \end{cases}$$ Case 2
$$\begin{cases} x \equiv 0 \pmod{2}\\ x \equiv 2 \pmod{3}\\ x \equiv 0 \pmod{5}\\ \end{cases}$$ Case 3 $$\begin{cases} x \equiv 1 \pmod{2}\\ x \equiv 2 \pmod{3}\\ x \equiv 1 \pmod{5}\\ \end{cases}$$ Case 4 $$\begin{cases} x \equiv 1 \pmod{2}\\ x \equiv 2 \pmod{3}\\ x \equiv 0 \pmod{5}\\ \end{cases}$$

Apply Chinese Remainder Theorem for the four system of equation, where $M = 30$:
$$\begin{cases} M_1 = \frac{30}{2} = 15\\ M_2 = \frac{30}{3} = 10\\ M_3 = \frac{30}{5} = 6\\ \end{cases}$$ And, $$\begin{cases} 15y_1 \equiv 1 \pmod{2} \implies y_1 = 1\\ 10y_2 \equiv 1 \pmod{3} \implies y_2 = 1\\ 6y_3 \equiv 1 \pmod{5} \implies y_3 = 1\\ \end{cases}$$

Therefore, the four solutions are: $$\begin{cases} x_1 = 1.15.0 + 1.10.2 + 1.6.1 = 26\\ x_2 = 1.15.0 + 1.10.2 + 1.6.0 = 20\\ x_3 = 1.15.1 + 1.10.2 + 1.6.1 = 41\\ x_4 = 1.15.1 + 1.10.2 + 1.6.0 = 35\\ \end{cases}$$

Edit
Add missing cases suggested by yunone
Case 5 $$\begin{cases} x \equiv 0 \pmod{2}\\ x \equiv 2 \pmod{3}\\ x \equiv 2 \pmod{5}\\ \end{cases}$$ Case 6 $$\begin{cases} x \equiv 1 \pmod{2}\\ x \equiv 2 \pmod{3}\\ x \equiv 2 \pmod{5}\\ \end{cases}$$

And the last two solutions are: $$\begin{cases} x_5 = 1.15.0 + 1.10.2 + 1.6.2 = 32 \equiv 2 \pmod{30}\\ x_6 = 1.15.1 + 1.10.2 + 1.6.2 = 47 \equiv 17 \pmod{30}\\ \end{cases}$$

Am I in the right track? Any idea?

Thanks,

-

So far this looks like you're on the right track. You may want to reduce the solutions $41$ and $35$ modulo $30$ to $11$ and $5$, respectively. Also, note that $x\equiv 2$ is a solution to $f(x)\equiv 0 \pmod{5}$, so you should address those two extra cases to find a total of $6$ solutions modulo $30$.

As a side note, you can use the $\LaTeX$ code \cdot to produce the multiplication symbol. For example, $30=2\cdot 3\cdot 5$ produces $30=2\cdot 3\cdot 5$.

-
 Thank you. I missed two cases. My bad! Also thanks for the Latex note. – Chan Mar 12 '11 at 21:52 @Chan, no problem. – yunone Mar 12 '11 at 21:54

With yunone's help you now have the six solutions modulo 30. But with questions like this it is often quicker, though perhaps less educational, to use brute force at least as a check.
So for $x$ in 0, 1, 2, 3, ..., 24 you find $6x^3 + 27x^2 + 17x + 20$ is

20, 70, 210, 476, 904, 1530, 2390, 3520, 4956, 6734, 8890, 11460, 14480, 17986, 22014, 26600, 31780, 37590, 44066, 51244, 59160, 67850, 77350, 87696, 98924, 111070, 124170, 138260, 153376, 169554

which is equivalent modulo 30 to

20, 10, 0, 26, 4, 0, 20, 10, 6, 14, 10, 0, 20, 16, 24, 20, 10, 0, 26, 4, 0, 20, 10, 6, 14, 10, 0, 20, 16, 24

and so the solutions are 2, 5, 11, 17, 20, and 26 modulo 30, more or less as you have.

-
A spreadsheet would make very quick work of this. Fill series will produce a column from 0 through 29, type the polynomial once, and copy down. – Ross Millikan Mar 13 '11 at 0:37
@Ross Millikan: which is how I got my numbers – Henry Mar 13 '11 at 1:05

$\rm\ mod\ 2\::\ \ 0\ =\ x^2 + x\ =\ x\ (x + 1)\ \ \Rightarrow\ \ x\ =\ 0,\:1$

$\rm\ mod\ 3\::\ \ 0\ =\: -x + 2\ \ \Rightarrow\ \ x\ =\ 2$

$\rm\ mod\ 5\::\ \ 0\ =\ x\ (x^2 - 3\ x + 2)\ =\ x\ (x-1)\ (x-2)\ \ \Rightarrow\ \ x\ =\ 0,\:1,\:2$

$\rm\ x = 2\ (mod\ 3)\ \Rightarrow\ x = 2,5,8,11,14\ (mod\ 15)\$ of which only $\rm\ S = \{2,5,11\}\$ are $\rm\ 0,1,2\ (mod\ 5)\:.\:$

So $\rm\ x \ \in\ S\: \cup\: (S+15)\ =\ \{2,5,11,17,20,26\}\ \ (mod\ 30)\$ since all values mod $2$ are solutions.

-