# how can I find an equivalent modulo to the system

I have to write an equivalent modulo to the system:

$\left\{\begin{matrix} x \equiv 1 \pmod 4\\ x \equiv 2 \pmod 3 \end{matrix}\right.$

That's what I have done so far:

$x \equiv 1 \pmod 4$

$x \equiv 2 \pmod 3$

$x=1+4k, k \in \mathbb{Z}$

$1+4k \equiv 2 \pmod 3 \Rightarrow 4k \equiv 1 \pmod 3$

Since, $(4,3)=1$,there is a solution.

$[4] [k]=[1] \text{ in } \mathbb{Z}_3$

$\Rightarrow [k]=[1] \text{ in } \mathbb{Z}_3$

$k=1+3l,l \in \mathbb{Z}$

But how can I find an equivalent modulo to the system??

-
en.wikipedia.org/wiki/Chinese_remainder_theorem or as lcm$(4,3)=12$ Check for $\pmod{12}$ to find $x\equiv5\pmod{12}$ – lab bhattacharjee May 1 '14 at 14:28
I got it!!!thanks a lot!!! – evinda May 1 '14 at 14:41

From

$4k \equiv 1 \pmod 3$

we have

$4k-3k \equiv 1-0 \pmod 3$

or

$k \equiv 1 \pmod 3$,

so $k=3l+1$.

$x=1+4k=1+4(3l+1)=1+12l+4=12l+5$

so $x \equiv 5 \pmod {12}$.

-
I understand...thank you very much!!! – evinda May 1 '14 at 14:40

Since $(4,3)=1$ work modulo $12$, when the conditions become:

$x\equiv 1, 5, 9$ and $x\equiv 2,5,8,11$, so $x\equiv 5 \mod 12$

With the Chinese Remainder Theorem we know there is a unique answer to such a pair of congruences. To this generally we note that we have $9\equiv 1 \mod 4$ is a multiple of $3$, and $4\equiv 1 \mod 3$ is a multiple of $4$ (we can always solve such congruences).

Then the solution to the problem $$x\equiv a \mod 4; x\equiv b\mod 3$$ becomes $$x\equiv 9a+4b \mod 12$$Clearly if $x=9a+4b$ the congruences modulo $3$ and $4$ are satisfied, and adding a multiple of $12$ won't change that.

So for the original problem $a=1, b=2, x\equiv 17\equiv 5 \mod 12$

-

Hint  The Chinese Remainder Theorem (CRT) is very easy when the $\color{#c00}{\rm Bezout}$ identity is known

$\qquad\color{#c00}{j m} + \color{#c00}{k n} = 1\ \Rightarrow\ \begin{eqnarray}&&x\equiv a\!\!\!\pmod m\\ &&x\equiv b\!\!\!\pmod n\end{eqnarray}$ $\!\iff\!\!$ $\begin{eqnarray} x&\equiv&\ a\,\color{#c00}{kn}\, +\, b\,\color{#c00}{jm}&&({\rm mod}\ {mn})\\ &\equiv& a+(b\!-\!a)\color{#c00}{jm}&&({\rm mod}\ mn)\end{eqnarray}$

In particular this is true when $\,m\ {\rm mod}\ n = 1,\,$ e.g. when $\ m-n = 1\,$ as in your case. viz.

$\ \color{#c00}{1\cdot 4} + \color{#c00}{(-1)3} = 1\ \Rightarrow\ \begin{eqnarray}&&x\equiv a\!\!\!\pmod 4\\ &&x\equiv b\!\!\!\pmod 3\end{eqnarray}$ $\!\iff\!\!$ $\begin{eqnarray} x&\equiv&\ a\,\color{#c00}{(-3)} + b\,\color{#c00}{(4)}&&({\rm mod}\ {mn})\\ &\equiv&\ a+(b\!-\!a)\,\color{#c00}{(4)}&&({\rm mod}\ mn)\end{eqnarray}$

-