# System of congruences and Chinese remainder theorem

Find all the integers satisfying this system of congruences $$\begin{cases} x \equiv 2 \pmod 5\\ x \equiv 1 \pmod {10}\\ x \equiv 0 \pmod 3 \end{cases}$$

I think you use Chinese remainder theorem but I'm not sure how to.

• Hint: $\ x\equiv 1\pmod{10}\,\Rightarrow\, x\equiv 1\pmod 5\ \$ – Bill Dubuque Jan 17 '15 at 17:33
• In general, if your moduli are not relatively prime, there will be restrictions on the residue classes like the one Bill mentions. – robjohn Jan 17 '15 at 17:37
• So is there no way of changing it so that it can be solved using Chinese remainder theorem? – Jack Jan 17 '15 at 17:39
• @Jack: you can change some of the numbers; for example, if you had $x\equiv7\pmod{10}$ instead of $1$, then there would be a solution. – robjohn Jan 17 '15 at 17:40
• Okay thanks a lot. Also if this were to have solutions then would you use Chinese remainder theorem? – Jack Jan 17 '15 at 17:44

As, $5|10,$

$$x\equiv1\pmod{10}\implies x\equiv1\pmod5$$

Again we have $x\equiv2\pmod 5$

But $1\not\equiv2\pmod5$

Hence there will be no solution

Hint $\ x\equiv 1\pmod{10}\,\Rightarrow\, x\equiv 1\pmod 5\$ contra $\ x\equiv 2\pmod 5$

Remark $\$ Generally we can employ the following criterion for existence of a solution

$$\begin{array}{} x\equiv a_1 \pmod{\!m_1 }\\ \quad \vdots \\ x\equiv a_k\pmod{\!m_k} \end{array}\ \text{is solvable}\ \iff\ \color{#c00}{a_i\equiv a_j}\!\!\!\! \pmod{\!\gcd(m_i,m_j)}\ \text{ for all }\ i,j$$

$(\Rightarrow)\$ has an easy proof:  if $\, d = \gcd(m_i,m_j)\,$ then $\,d\mid m_i,m_j\,$ so $\ {\rm mod}\ d\!:\ \color{#c00}{a_i\equiv x\equiv a_j}\$

Basically the two equivalences \begin{align} x &\equiv a \pmod A \\ x &\equiv b \pmod B \end{align} have a common solution if and only if $$a \equiv b \pmod{\gcd(A,B)}$$

In the case of \begin{align} x &\equiv 2 \pmod 5\\ x &\equiv 1 \pmod {10}\\ x &\equiv 0 \pmod 3 \end{align}

We notice that $1 \not \equiv 2 \pmod{\gcd(5,10)}$, so there is no common solution to all three equivalences.

Another method is to reduce each equivalence into prime-power congruences and then remove redundant equivalneces. If there are no contradictory congruences , what you are left with is amenable to the regular CRT.

for your problem, $x \equiv 2 \pmod 5$ and $x \equiv 0 \pmod 3$ are already prime-power congruences. Since $10 = 2 \times 5$ we can break $x \equiv 1 \pmod {10}$ into the two prime-power congruences

\begin{align} x &\equiv 1 \pmod {2} \\ x &\equiv 1 \pmod {5} \end{align}

and we notice that $x \equiv 1 \pmod {5}$ and $x \equiv 2 \pmod {5}$ contradict each other. So, again, we know that the system of congruences has no common solution.