How to solve modular arithmetics problems, that are not linear?

Question

$2x^{20} + 3x + 4 \equiv 0 $(mod 176)

I know the answer is $x = 176k + 20$, $k \in \mathbb{Z}$ , but I don't know, how to solve this problem.

Answer 1

$176=2^411$.

Mod $2^4=16$:

If $\gcd(16,x)>1$, it's $3x+4\equiv0\bmod16$ or $3x\equiv12\bmod 16$ or $x\equiv4\bmod 16.$

If $\gcd(16,x)=1,$ $2x^{20}+3x+4\equiv0\bmod 16$ has no solutions,

because $3x\equiv0\bmod2$ has no solutions with odd $x$.

Mod $11$:

If $\gcd(11,x)>1,$ it would be $4\equiv0\bmod11$ and there are no solutions.

If $\gcd(11,x)=1$, then by Fermat's little theorem it $x^{20}\equiv x^{10}\equiv 1\bmod11$,

and it would be $2+3x+4\equiv0\bmod11$ or $3x\equiv-6\bmod11$ or $x\equiv-2\bmod11$.

---

Can you solve $x\equiv4 \bmod16$ and $x\equiv9\bmod11$ using the Chinese remainder theorem?

Answer 2

Fermats little theorem and Eulers theorem and/or chinese remainder can reduce $x^{20}$ to something smaller and factoring/quadratic formula is still valid.

$176 = 11*16$.

To solve $2x^{20}+3x +4 \equiv 0 \pmod{11}$ we have $x\not \equiv 0 \pmod {11}$ (obviously) so $x^{10} \equiv 1$ and so $3x + 6 \equiv 0$ and it is linear $3x \equiv -6 = \pmod{11}$ and $x \equiv -2\equiv 9 \pmod {11}$.

To $x^{20}+3x + 4\equiv 0 \pmod{16}$ if $x$ is even then $x^4|x^{20}$ so $2x^{20}+3x +4\equiv 3x + 4 \equiv 0\pmod {16}$. $3x \equiv -4 \equiv 12 \pmod{16}$ and $\gcd(3,12)=1$ so $3$ is invertible so $x \equiv 4\pmod {16}$.

If $x$ is odd then $\phi(16)= 8$ so $x^{20}\equiv x^4$ and we have $2x^4+3x +4\equiv 0\pmod{16}$ and, well, $3x$ is odd but $2x^4 + 4$ is even so there is not solution.

So we one solution

$x\equiv 9 \pmod {11}; x\equiv 4 \pmod 16$ or the one unique solution (its unique because CRT tells us so) $x\equiv 20\pmod {176}$