Solve $x^3+3x^2-6x-88\equiv0\bmod{402}$

Question

$$x^3+3x^2-6x-88\equiv0\bmod{402}$$

I think I should solve modulo $2$, $3$ and $67$. I can solve modulo $2$ and $3$ but how to solve for modulo $67$? Also need help to combine the solutions for modulo $402$.

Answer 1

In the comments, the given polynomial has been factored over $\mathbb F_{67}$ into $(x-4)(x^2+7x+22)$, giving $x=4$ as a solution. What about $x^2+7x+22$? Can this be zero?

Completing the square algebraically gives $$(x+7/2)^2-49/4+22=0$$ The inverse of 2 in $\mathbb F_{67}$ is 34 and that of 4 is 17, so we can replace the divisions by multiplications: $$(x+7\cdot34)^2-49\cdot17+22\equiv0\bmod67$$ $$(x+37)^2\equiv7\bmod67$$ Computing the Legendre symbol $\left(\frac7{67}\right)$, however, gives $-1$, so 7 has no square root in $\mathbb F_{67}$. Thus, the only solution of the original polynomial in $\mathbb F_{67}$ is $x\equiv4$.

We also know that the solutions in $\mathbb F_2$ and $\mathbb F_3$ are $x\equiv0,1$ and $x\equiv1$ respectively, so we can use the Chinese remainder theorem to give all solutions in $\mathbb F_{402}$. The final answer is thus $$x\equiv4\bmod402\lor x\equiv205\bmod402$$