# Chinese Remainder Theorem Problem

I’m working on some Chinese Remainder problems and it doesn’t seem like I have the procedure down correctly. I’ll list the steps I’m taking so hopefully someone can spot what it is I’m doing wrong.

Find the least nonnegative solution of each system of congruences below.

$x \equiv 3 \space mod \space 4$

$x \equiv 2 \space mod \space 5$

Since the mod values are relatively prime, I preformed the following procedure described in my textbook. Let $M = m_{1} \cdot m_{2} \cdot \cdot \cdot m_{n}$ and $M_{i} = \frac{M}{m_{i}}$

$M = (4) \cdot (5) = 20$

$M_{1} = \frac{20}{4} = 5$

$M_{2} = \frac{20}{5} = 4$

Next solve the congruence $M_{i} x_{i} \equiv \text{1 mod} \space m_{i}$ for $x_{i}$

$5x_{1} \equiv \text{1 mod} \space 4$ $\Longrightarrow$ $x_{1} \equiv 1 \space \text{mod} \space 4$

$2x_{2} \equiv \text{1 mod} \space 5$ $\Longrightarrow$ $x_{2} \equiv 3 \space \text{mod} \space 5$

Finally solve for x, where x is defined in the following way: $x = b_{1} \cdot M_{1} \cdot x_{1} + \cdot \cdot \cdot + b_{n} \cdot M_{n} \cdot x_{n}$

$x = (3 \cdot 5 \cdot 1) + (2 \cdot 4 \cdot 3) \space \text{mod} \space 20$

$x = 19 \space mod \space 20$

Now this final value indicates that any positive integer congruent to 19 modulo 20 solves the given system of equations. However, the answer at the back of my textbook is 7 which isn’t congruent to 19 modulo 20.

Any help with where I’m going wrong would be appreciated

#### Solutions Collecting From Web of "Chinese Remainder Theorem Problem"

Note that your solution is incorrect since $x \equiv 19 \pmod{20}$ gives $x \equiv 4 \pmod {20}$. You need to solve for $$\color{blue}{4 x_2 \equiv 1 \pmod5}$$ and not $$\color{red}{2x_2 \equiv 1 \pmod 5}$$ Hence, you will get that
$$\color{blue}{x_2 \equiv 4 \pmod 5}$$ and not $$\color{red}{x_2 \equiv 3 \pmod 5}$$ The rest of your derivation is correct. Make the above correction and you will get the right answer.

The second case should be $x_2\cdot \frac{20}5\equiv1\pmod 5$

$\implies 4x_2\equiv1\pmod 5\implies -x_2\equiv1\pmod 5\implies x_2\equiv-1\pmod 5\equiv4\pmod 5$

So, $x\equiv3\cdot5\cdot1+2\cdot4\cdot4\pmod{20}\equiv47\equiv7\pmod{20}$

I noticed something very interesting: there are many implementations of the Chinese Remainder Theorem.

Chinese Remainder Theorem:

A theorem for solving a system of linear congruences, which come in the form

$\displaystyle x\equiv n_1\pmod{m_1}$

$\displaystyle x\equiv n_2\pmod{m_2}$

$\displaystyle \vdots$

$\displaystyle x\equiv n_k\pmod{m_k}$

Where $\displaystyle k\in\mathbb{N}$ and $\displaystyle m_1, m_2\cdots m_k$ are pairwise coprime, then $\displaystyle x_0=B_1X_1n_1+B_2X_2n_2+\cdots+B_kX_kn_k$ where $\displaystyle B=\prod_{i=1}^{k}m_i$ and $\displaystyle B_k=\frac{B}{m_k}$ and $\displaystyle X_k$ is defined so that $\displaystyle B_kX_k\equiv1\pmod{m_k}$.

The smallest positive integer solution $\displaystyle x_1$ is defined such that $\displaystyle x_0\equiv x_1 \pmod{B}$

For this system where it is

$\displaystyle x \equiv 3 \pmod{4}$

$\displaystyle x \equiv 2 \pmod{5}$

$\displaystyle B = 4\times5 = 20$

$\displaystyle B_1=\frac{20}{4}=5$, $\displaystyle B_2=\frac{20}{5}=4$

$\displaystyle 5X_1\equiv1\pmod{4} \iff X_1\equiv1\pmod{4}$, $\displaystyle X_1=1$

$\displaystyle 4X_2\equiv1\pmod{5}$, $\displaystyle X_2=4$

$\displaystyle x=5\times1\times3+4\times4\times2=47$

$\displaystyle 47 \equiv 7\pmod{20}$

That is why your textbook says the answer if $\displaystyle 7$.