Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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
1  
@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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.