$(1)$ Find all $x$, that solve $7x^2 + x + 22 \equiv 0 \pmod{60}$.
I tried to solve this by first considering the prime factorization $60 = 2^2\cdot 3\cdot 5$ and then using the Chinese Remainder Theorem, that is for $n_1, …, n_k$ coprime and $a_1, …, a_k$ there exists a $x \in \mathbb{Z}$ that solves the system of simultaneous congruences
\begin{cases} x \equiv a_1 & \pmod{n_1} \\ \quad \cdots \\ x \equiv a_k &\pmod{n_k} \end{cases}
In this case i just tried to find a solution to $(1)$ mod $3$, mod $4$, mod $5$ one at a time by testing $0,1,2$, $0,1,2,3$ and $0,1,2,3,4$ respectively. While all of the congruences have solutions I couldn't find a single $x \in \mathbb{Z}$ that solves all of them. However, Wolfram-Alpha says there are two solutions $x_1 = 31$ and $x_2 = 46$. So how do I apply the CRT to this in the correct way?
Best Answer
By CRT $7x^2+x\equiv -22\equiv 38 \bmod 60$ if and only if:
$x(7x+1)\equiv x(3x+1)\equiv 2 \bmod 4$
$x(7x+1)\equiv x(x+1) \equiv 2 \bmod 3$
$x(7x+1)\equiv x(2x+1) \equiv 3 \bmod 5$
Finding the solutions to each of these can be done by hand.
You want numbers such that:
$x\equiv 2$ or $3\bmod 4$
$x\equiv 1 \bmod 3$
$x\equiv 1 \bmod 5$.
By CRT there is one congruence when $x\equiv 2\bmod 4$ and another when $x\equiv 3\bmod 4$
I will solve the first of these, the other one is analogous. We use the algebraic approach explained in wikipedia:
$x\equiv2\bmod 4$
$x\equiv 1\bmod 3$
$x\equiv 1 \bmod 5$
We have $x=2+4t$ so $2+4t\equiv 1 \bmod 3$ so $4t\equiv 2 \bmod 3\implies t\equiv 2 \bmod 3\implies t=2+3k$. Therefore $x=2+4(2+3k)=10+12k$.
We now have $x=10+12k\equiv 1 \bmod 5\implies 12k\equiv 1 \bmod 5\implies 2k\equiv 1\bmod 5\implies k\equiv 3 \bmod 5$. therefore $k=5s+3$
So $x=10+12(5s+3)=60s+46$. So $x\equiv 46 \bmod 60$