2
$\begingroup$

Can anyone solve the following system of congruences using CRT step-wise, without skipping any part?

$$\begin{cases} x\equiv 3 \pmod{7}\\ x\equiv 3 \pmod{13}\\ x\equiv 0 \pmod{12}\end{cases}$$

The answer to this problem $276$ but, I keep getting the answer $264$. What is it that I am doing wrong?

$\endgroup$
  • 2
    $\begingroup$ Note that $264\equiv 5\pmod{7}$ and $264\equiv 4\pmod{13}$, so $264$ is not right. $\endgroup$ – André Nicolas Mar 24 '15 at 2:46
  • $\begingroup$ 276≡3(mod7) and 276≡3(mod13), 276 is the right answer $\endgroup$ – Shounak Katyayan Mar 24 '15 at 2:59
1
$\begingroup$

$x$ is a multiple of $12$ so $x=12k$. We also have $12k\equiv 3\bmod 7$, $12$ is congruent to $5\bmod 7$ and the inverse of $5\bmod 7$ is $3$ by inspection. So $k\equiv 3\cdot5\cdot k\equiv 3\cdot3\equiv 2\bmod 7$. Therefore $k$ is $7l+2$.

So $x=12(7l+2)=84l+24$.

We now have $84l+24\equiv 3 \bmod 13$. This tells us $84l\equiv 5 \bmod 13\implies 6l\equiv 5 \bmod 13$. The inverse of $6\bmod 13$ is $11$ by inspection, therefore $l\equiv 11\cdot 6 \cdot l\equiv 11\cdot 5\equiv 3 \bmod 13$. Therefore $l=13j+3$

And so $x=84l+24=84(13j+3)+24=1092j+276$.

So indeed the solution is to take $n\equiv 276\bmod 1092$. And by the chinese remainder theorem the solution is unique.

$\endgroup$
1
$\begingroup$

$12\mid x\,\Rightarrow\, x=12y.\ $ And $\ 7,13\mid x\!-\!3\!\iff\! \overbrace{{\rm lcm}(7,13)}^{\large 91}\mid x\!-\!3\!\iff\! x\equiv\color{#c00} 3\pmod{91}$

$\ {\rm mod}\ 91\!:\ x = 12y\equiv\color{#c00} 3\iff y\equiv \dfrac{3}{12}\equiv \dfrac{1}4\equiv \dfrac{92}4\equiv \color{}{23}\!\iff\! \color{#0a0}{y = 23+91n} $

Therefore $\, x = 12\color{#0a0}y = 12(\color{#0a0}{23 + 91n}) = 276 + 1092k$

$\endgroup$
  • $\begingroup$ Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion. $\endgroup$ – Bill Dubuque Mar 24 '15 at 3:01
0
$\begingroup$

The first pair of congruences would give the result of:

$x \equiv3 \mod 91$

Thus, the next part is solving 3+91a being a multiple of 12 which could be reduced to 3+7a where one could do trial and error to find a=3 would be a solution as 3+7*3=3*8=24.

3+91*3=3*92=276.

$\endgroup$
0
$\begingroup$

I directly use the result (formula) for Chinese Remainder Theorem to solve this problem. By the way, this method needs a little knowledge of group theory.

For the system $$x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\ \vdots\\ x\equiv a_n\pmod{m_n}$$ The general solution is given by $$x=\sum_{i=1}^na_iM_iy_i+t\cdot \prod_{i=1}^nm_i,$$ where $$t\in\mathbb{Z},\qquad M_i=\prod_{j=1,\ j\neq i}^nm_j\qquad \text{and}\qquad [M_iy_i]_{m_i}=[1]_{m_i}.$$

Therefore, in this problem, $a_1=3,\ m_1=7, a_2=3,\ m_2=13,\ a_3=0,\ m_3=12$,
we have $$M_1=13*12=156,\quad y_1=4$$ $$M_2=7*12=84,\quad y_2=-2$$ $$M_3=7*13=91,\quad y_3=-5$$ So the solution is $x=3*4*156-3*2*84-0*5*91+7*13*12*t=1368-1092t$. For your answer, it is just the smallest positive solution, which can be obtained from letting $t=1$, $1368-1092=276$.

$\endgroup$

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.