# Solve simultaneous systems of congruences $x\equiv 10 \pmod{60}$ and $x\equiv 80 \pmod{350}$

Solve simultaneous systems of congruences $$x\equiv 10 \pmod{60}$$ and $$x\equiv 80 \pmod{350}$$

How does one solve this using CRT? Because it has duplicate primes in its factorization? I got

$$350=5*5*2*7$$
$$60=2*2*3*5$$

So I tried CRT with

$$x\equiv 1\pmod3, x\equiv0\pmod5, x\equiv0 \pmod2, x\equiv3 \pmod7$$ and got the wrong answer.

or should it be
$$x\equiv 1\pmod3, x\equiv5\pmod{25}, x\equiv2\pmod4, x\equiv3\pmod7$$

• it should be the latter Dec 1 '19 at 0:23

## 3 Answers

Your work will be greatly simplify using the formula for the solutions of a system of two simultaneous congruences with coprime moduli $$a$$ and $$b$$ based on Bézout's identity $$ua+vb=1,\qquad(u,v\in\mathbf Z):$$ $$\begin{cases} x\equiv \alpha\mod a\\x\equiv\beta\mod b \end{cases}\iff x\equiv\beta\,ua+\alpha\,vb\mod ab.$$ Now your congruences are equivalent to $$\begin{cases}x'\equiv 1\mod 6\\x'\equiv8\mod 35 \end{cases}$$ and $$x\equiv 10x'\mod60\cdot 350$$.

Added:

The given congruences mean there exist $$k,l \in\mathbf Z$$ such that $$x=10+60k=80+350l$$, i.e. $$x=10(1+6k)=10(8+35l)$$, so $$1+6k=8+35l$$, which I denote $$x'$$, whence the simplified system of congruences and the relation between $$x$$ and $$x'$$. congruences

• Sorry could you show your steps I'm a bit confused Nov 30 '19 at 10:22
• @user8714896, first you reduce your mods $60$ and $350$ by dividing them by their greatest common divisor $10$, getting relatively prime mods $6$ and $35$, and the induced congruences (divide by $\gcd$). THEN you solve the obtained reduced system. Then unreduce (multiply by $\gcd$). Nov 30 '19 at 10:44
• @user8714896: I've added an explanation. Is that clearer? Nov 30 '19 at 11:00

When the moduli are not coprime there may not be a solution. With a small system, it's probably better to solve in the following fashion so that you can see when and why a contradiction arises:

From the first congruence you have $$x=10+60y$$. Plug that into the second congruence to get

$$10+60y \equiv 80 \pmod{350}$$

$$60y \equiv 70 \pmod{350}$$

$$6y \equiv 7 \pmod{35}$$

$$6$$ is its own inverse mod $$35,$$ so we have

$$y \equiv 42 \equiv 7 \pmod{35}$$ or $$y=42+35k$$.

Then $$x = 10 + 60 (42 +35k) = 2530+2100 k$$, or if you shift $$k$$ by one, $$x = 430 +2100k$$.

• What do you mean by "$6$ is its own inverse $\pmod{35}$"? Do you mean $6\equiv6^{-1}\pmod{35}$? Dec 1 '19 at 1:00
• @manooooh Yes. $6\cdot 6 \equiv 1 \pmod{35}.$ Dec 1 '19 at 2:23

It should be $$\color{magenta}{x\equiv 1\pmod3}, \color{blue}{x\equiv5\pmod{25}}, \color{magenta}{x\equiv2\pmod4,} \color{brown}{x\equiv3\pmod7}$$.

From $$\color{magenta}{x\equiv-2\pmod{3,4}}$$ we get $$x\equiv-2\equiv10\mod12.$$

From $$x\equiv10\pmod{12}$$ and $$\color{blue}{x\equiv5\pmod{25}},$$ we get $$x\equiv130\pmod{300}$$.

From $$x\equiv130\pmod{300}$$ and $$\color{brown}{x\equiv3\pmod7}$$, we get $$x\equiv430\pmod{2100}$$.