0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

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

${\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}.$

$\endgroup$
0
$\begingroup$

$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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.