System of congruences and Chinese remainder theorem

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.