I have found the following congruences:

  1. $x \equiv 2\mod 5$
  2. $x \equiv 12\mod27$
  3. $x \equiv 2\mod4$

How can I solve for x using the Chinese Remainder Theorem? Please include justifications for the steps you take.

How can I find $x$?


4 Answers 4


Hint $\ $ Note that by the constant-case optimization of CRT we have

$$\rm\begin{eqnarray} x\equiv 2\pmod 4\\\rm x\equiv 2\pmod 5\end{eqnarray}\ \iff\ x\equiv 2\pmod{4\cdot 5}$$

Now applying Easy CRT to the RHS congruence and the remaining congruence we obtain

$$\rm\begin{eqnarray} x\equiv \color{#C00}2\pmod{\color{blue}{20}}\\\rm x\equiv \color{#0A0}{12}\pmod{27}\end{eqnarray}\ \iff\ x\equiv \color{#0A0}{12}+27\,\left[\dfrac{\color{#C00}2\!-\!\color{#0A0}{12} }{27}\ mod\ \color{blue}{20}\right]\equiv 282\pmod{\color{blue}{20}\cdot 27}$$

where the above fraction is computed as $\rm\, mod\ 20\!:\ \dfrac{10}{27}\equiv \dfrac{10}{7}\equiv\dfrac{30}{21}\equiv \dfrac{10}1,\ $ and $\rm\:-10\equiv 10$

  • $\begingroup$ I like the look of this "Easy CRT" method. However, could you apply some intuition on why the formula works? I read the hyperlinked proof you gave in another question and it is not clear for a novice like myself. $\endgroup$ Sep 23, 2012 at 22:39
  • $\begingroup$ @Code I added a note to the Easy CRT link showing how the solution is derived and easily remembered. $\endgroup$ Sep 23, 2012 at 23:11

The first thing to look for is that your moduli are pairwise coprime - they are. Good. We consider that our system is of the form $x \equiv a_i \pmod{m_i}$. So, let $a_1 = 2$, $a_2 = 12$, and $a_3 = 2$. Further, let $m_1 = 5$, $m_2 = 27$, and $m_3 = 4$, then

$M_1 = m_2 m_3$,

$M_2 = m_1 m_3$, and

$M_3 = m_1 m_2$.

Now we solve (usually by the Euclidean algorithm, or by inspection for smaller numbers that are somewhat obvious) for each $y_i$ where

$y_1 M_1 \equiv 1 \pmod{m_1}$,

$y_2 M_2 \equiv 1 \pmod{m_2}$, and

$y_3 M_3 \equiv 1 \pmod{m_3}$.

Then our solution that satisfies all three equivalences is

$x \equiv a_1 y_1 M_1 + a_2 y_2 M_2 + a_3 y_3 M_3 \pmod{m_1 m_2 m_3}$

I trust you can take the arithmetic from here.


This particular one can go manually:

From 1. and 3. we get $x\equiv 2 \mod 20$, so we need an $x$ among $2,22,42,62,\ldots$ which is $\equiv 12 \mod 27$. Subtracting $12$, it is $-10,10,30,50,\ldots,270,\ldots$.

So, $x\equiv 282 \mod (20\cdot 27)$.


I will assume that you are partly familiar with the machinery of CRT.

We want to first find $a, b,c$ such that $a(27)(4)\equiv 1\pmod{5}$, and $b(5)(4)\equiv 1\pmod{27}$, and $c(5)(27)\equiv 1\pmod{7}$. Then a solution of our system of congruences is $$x=2(a)(27)(4)+12(b)(5)(4)+2(c)(5)(27).$$ It may be that the $x$ we obtain is kind of large, and we may want to replace it by something congruent to it modulo $(5)(27)(4)=540$ that is, say, in the interval $[0,539]$.

Let's find suitable $a$, $b$, and $c$. In general for this work, and with large moduli, we would use the Extended Euclidean Algorithm. Let's not bother, since we are concentrating on CRT.

For $a$, work modulo $5$. Since $27$ is congruent to $2$, we want $8a\equiv 1\pmod{5}$, or equivalently $3a\equiv 1\pmod{5}$. So we can take $a=2$. Or maybe $a=-3$. Doesn't matter.

For $b$, we want $20b\equiv 1\pmod{27}$. Slightly unpleasant, but note that $(20)(4)\equiv -1\pmod{27}$, so we can take $b=-4$.

For $c$, the modulus is tiny. We want $c(5)(27)\equiv 1\pmod{4}$. But $5$ is congruent to $1$, and $27$ is congruent to $3$, so we can take $c=3$.

Remark: But we can take a bit of a shortcut. Note that we wanted $x\equiv 2\pmod{5}$ and $x\equiv 2\pmod{4}$. This is the case iff $x\equiv 2\pmod{20}$. So we want to solve the system of congruences $x\equiv 2\pmod{20}$, $x\equiv 12\pmod{27}$. This is a two congruence CRT problem. We find $a$ and $b$ such that $a(27)\equiv 1\pmod{20}$ and $b(20)\equiv 1\pmod{27}$. Then we can take $$x=2(a)(27)+12(b)(20).$$ For $a$, it is clear that $3$ will do. For $b$, $-4$ works. This gives answer $2(3)(27)+12(-4)(20)$. For something in the range $[0.539]$, add $(2)(540)$. We get $x=282$. So the general solution is $x\equiv 282\pmod{540}$.


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.