Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
add comment

4 Answers

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.

share|improve this answer
add comment

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$

share|improve this answer
    
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. –  CodeKingPlusPlus Sep 23 '12 at 22:39
    
@Code I added a note to the Easy CRT link showing how the solution is derived and easily remembered. –  Bill Dubuque Sep 23 '12 at 23:11
add comment

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)$.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.