Solve the non-linear congruence $x^3+2x^2+5x+4\equiv 0\pmod {60}$.

Question

Solve the non-linear congruence $x^3+2x^2+5x+4\equiv 0\pmod {60}$.

For this question, I think I might need to use the Chinese remainder Theorem to simplify the problem to several smaller moduli (e.g. possibly $\pmod 4,\pmod 5,\pmod 3$ and simplify the $x^3+2x^2+5x$ terms).

Answer 1

It's easy to find the roots mod $3,4,5$ as in J.W.T's answer. But lifting these to roots $\bmod 60$ is a pain by the CRT formula. Easier is to sieve. $\,x\equiv 2,4\pmod{\!5}\,$ so we list these values $\!\bmod 60$ in an array, where the first row $\equiv 2,\,$ the second $\,\equiv 4\pmod{\!5},\,$ as below.

$\begin{array}{c} 2^4\!\!\!\!\! &&\!\!\!\!\! \color{#c00} 7\!\!\!\!\! &&\!\!\!\!\! 12_3\!\!\!\!\! &&\!\!\!\!\! \color{#c00}{17}\!\!\!\!\! &&\!\!\!\!\! 22^4\!\!\!\!\! &&\!\!\!\!\! 27_3\!\!\!\!\! &&\!\!\!\!\! \color{#c00}{32}\!\!\!\!\! &&\!\!\!\!\! \color{#c00}{37}\!\!\!\!\! &&\!\!\!\!\! {42_3}^{\!\!4}\!\!\!\!\! &&\!\!\!\!\! \color{#c00}{47}\!\!\!\!\! &&\!\!\!\!\! \color{#c00}{52}\!\!\!\!\! && \!\!\!\!\! 57_3 \\ & \color{#c00}4 && 9_3 && 14^4 &&\color{#c00}{19} && 24_3 && \color{#c00}{29} && 34^4 && 39_3 && \color{#c00}{44} && \color{#c00}{49} && {54_3}^{\!\!4} && \color{#c00}{59} \end{array}$

Next we know $\,x\equiv 1,2\pmod{\!3}$ so we need to exclude all multiples of $3$, which are $\,12+15n\,$ in the first row, and $\,9+15n\,$ in the second, which we mark with a subscript $3$. Finally we know $\,x\equiv 0,1,3\pmod{\!4},\,$ so we need to exclude all $\,x\equiv 2\pmod{\!4},\,$ which are $\,2+20n\,$ in the first row, and $\,14+20n\,$ in the second, which we mark with a superscript $4$. The $\color{#c00}{12}$ remaining $\color{#c00}{\rm nonscripted}$ entries are all the the solutions $\!\bmod 60$.

Answer 2

Modulo $4$ we have $x^3+2x^2+x=x(x+1)^2\equiv0$,

which means $x\equiv0$ or $x+1\equiv2$ or $4$.

Modulo $5$ we have $x^3+2x^2+5x+4=(x+1)(x^2+x+4)\equiv(x+1)(x-2)^2\equiv0$,

which means $x\equiv 4$ or $2$.

Modulo $3$ we have $x^3+2x^2+5x+4=(x+1)(x^2+x+4)\equiv(x+1)(x-1)^2\equiv0$,

which means $x\equiv 2$ or $1$.

Can you take it from here with the Chinese remainder theorem

to find $12$ solutions modulo $60=4\times5\times3$?