Solving a quadratic congruence with Chinese Remainder Theorem How can quadratic congruences like $4u^2+10u+128 \equiv 0\pmod{116}$ be solved? I had no problems splitting the congruence into two parts,$\equiv0\pmod4$ and $\equiv 0\pmod{29}$, getting the solutions $u\equiv0, 2\pmod4$ and $u\equiv4,8\pmod{29}$. But I don’t know how to combine these to solve the original congruence mod 116. I suppose the Chinese Remainder Theorem is involved, but I don’t know how to apply it. Any help is greatly appreciated. Thanks!
 A: Chinese Remainder Theorem
Since $\gcd(4,29)=1$, then by Bezout's identity, which can be solved using the extended Euclidean algorithm or by trial and error for small numbers, we get:
$$
4a+29b=1
$$
which implies:
$$
\begin{align}
A=29b&=1\pmod4\\
B=4a&=1\pmod{29}
\end{align}
$$
Therefore:
$$
N=Ax+By\\
\Updownarrow\\
\begin{align}
N&=x\pmod4\\
N&=y\pmod{29}
\end{align}
$$
So to solve a given pair of congruences modulo $4$ and $29$, you need to do the steps above:

*

*Determine $a,b$

*Compute $A,B$ (and reduce them modulo 116)

*Pick the pair $x,y$ from your solutions to the two respective congruences

*Compute $N$ (and reduce modulo 116)


Let us do some of it here, then you can finish:

*

*Trial and error of Bezout: We have $29\cdot 1=1\pmod4$. Therefore $29\cdot3+1=0\pmod4$. And $29\cdot3+1=88=4\cdot22$. So to sum up:
$$
\begin{align}
29&=1\pmod{4}\\
88&=1\pmod{29}
\end{align}
$$

*Now we pick $x,y$. Let us take $N=2\pmod4$ and $N=8\pmod{29}$, so that we have $x=2$ and $y=8$.

*Finally compute:
$$
N=2\cdot29+8\cdot88=66\pmod{116}
$$
And if your partial congruences were right, we should have $u=66$ as one solution to the equation. You will get four solutions as a total by combining the possible values of $x,y$ from the two partial congruences.

