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.

  • 2
    $\begingroup$ Hint: $\ x\equiv 1\pmod{10}\,\Rightarrow\, x\equiv 1\pmod 5\ \ $ $\endgroup$ – Bill Dubuque Jan 17 '15 at 17:33
  • $\begingroup$ In general, if your moduli are not relatively prime, there will be restrictions on the residue classes like the one Bill mentions. $\endgroup$ – robjohn Jan 17 '15 at 17:37
  • $\begingroup$ So is there no way of changing it so that it can be solved using Chinese remainder theorem? $\endgroup$ – Jack Jan 17 '15 at 17:39
  • $\begingroup$ @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. $\endgroup$ – robjohn Jan 17 '15 at 17:40
  • $\begingroup$ Okay thanks a lot. Also if this were to have solutions then would you use Chinese remainder theorem? $\endgroup$ – 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.


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.