3
$\begingroup$

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,

3 Answers 3

3

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

  • 0
    @Chan, no problem.2011-03-12
2

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.

  • 1
    @Ross Millikan: which is how I got my numbers2011-03-13
2

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