[Math] Chinese Remainder Theorem Problem

elementary-number-theory

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

Best Answer

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.

Related Question