# How to solve this quadratic congruence modulo a non-prime number

$(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?

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$

• Thanks, but I still don't get how there can be a solution to this system of congruences if there is no x that solves all of them. 2 and 3 solve the congruence mod 4, 1 solves mod 3 and also mod 5. How can there be a solution? The CRT says there is at least one that solves them all at the same time. Where's my misconception? Feb 15, 2015 at 2:40
• also how do I compute the solutions to the congruence mod 60 with these? Feb 15, 2015 at 2:42

${\rm mod}\,\ 15\!:\,\ 0\,\equiv -2f \equiv\, x^2\!-2x+1\equiv (x-1)^2\!\iff x\equiv 1.\,\$ So $\,\ x\equiv 1,16,31,46\pmod{60}$
but mod $\,4\!:\,$ only $\ 31\equiv -1,\,\ 46\equiv 2\,$ are roots of $\,f\equiv\, -x^2\!+x+2.\,$ So $\ x\equiv 31,46\pmod{60}.$