# 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? – jazzinsilhouette Feb 15 '15 at 2:40
• also how do I compute the solutions to the congruence mod 60 with these? – jazzinsilhouette Feb 15 '15 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}.$

$7x^2 + x + 22 \equiv 0 \pmod{60}$

First of all, $\frac 17 \equiv -17 \pmod{60}$, so you can get a simpler quadradic by multiplying both sides by $-17$.

$x^2 -17x + 46 \equiv 0 \pmod{60}$

Modulo $3$, we get $x^2 - 2x + 1 \equiv (x-1)^2 \equiv 0 \pmod 3$, so $x \equiv 1 \pmod 3$

Modulo $4$, we get $x^2 - x - 2 \equiv (x+1)(x-2) \equiv 0 \pmod 4$, so $x \equiv 2, 3 \pmod 4$

Modulo $5$, we get $x^2 - 2x + 1 \equiv (x-1)^2 \equiv 0 \pmod 5$, so $x \equiv 1 \pmod 5$

Now we note that

$$40 \pmod{60} \equiv \left\{ \begin{array}{c} 1 \pmod 3\\ 0 \pmod 4\\ 0 \pmod 5 \end{array} \right. \tag{A}$$

$$45 \pmod{60} \equiv \left\{ \begin{array}{c} 0 \pmod 3\\ 1 \pmod 4\\ 0 \pmod 5 \end{array} \right. \tag{B}$$

$$36 \pmod{60} \equiv \left\{ \begin{array}{c} 0 \pmod 3\\ 0 \pmod 4\\ 1 \pmod 5 \end{array} \right. \tag C$$

So

$x \equiv 40(1) + 45(2) + 36(1) \equiv 46 \pmod{60}$

or

$x \equiv 40(1) + 45(3) + 36(1) \equiv 31 \pmod{60}$

## Notes

(A) If $n \equiv 0 \pmod 4$ and $n \equiv 0 \pmod 5$, then $n \equiv 0 \pmod{20},$

that is $n = 20m$ for some integer $m$. So

\begin{align} n &\equiv 1 \pmod 3 \\ 20m &\equiv 1 \pmod 3\\ 2m &\equiv 1 \pmod 3\\ m &\equiv 2 \pmod 3 \\ n &\equiv 40 \pmod{60} \end{align}

(B) If $n \equiv 0 \pmod 3$ and $n \equiv 0 \pmod 5$, then $n \equiv 0 \pmod{15},$

that is $n = 15m$ for some integer $m$. So

\begin{align} n &\equiv 1 \pmod 4 \\ 15m &\equiv 1 \pmod 4\\ -m &\equiv 1 \pmod 4\\ m &\equiv 3 \pmod 4 \\ n &\equiv 45 \pmod{60} \end{align}

(C) If $n \equiv 0 \pmod 3$ and $n \equiv 0 \pmod 4$, then $n \equiv 0 \pmod{12},$

that is $n = 12m$ for some integer $m$. So

\begin{align} n &\equiv 1 \pmod 5 \\ 12m &\equiv 1 \pmod 5\\ 2m &\equiv 1 \pmod 5\\ m &\equiv 3 \pmod 5 \\ n &\equiv 36 \pmod{60} \end{align}