# Simple exersice using CRT

Calculate all solutions $0\leq x< 130$ for the following system of equations.

$x \equiv_2 1$

$x \equiv_5 2$

$x \equiv_{13} 3$

Solution:

$M=2\cdot 5\cdot 13=130$

So by CRT there exists a unique solution.

We get:

$M_1=M/2=65$

$M_2 = M/5 = 26$

$M_3=M/13=10$

Now:

$65\cdot N_1 \equiv_2 1 \ \ \Rightarrow \ \ N_1 = 1$

$26\cdot N_2 \equiv_5 2 \ \ \Rightarrow \ \ N_2=2$

$10\cdot N_3 \equiv_{13} 3 \ \ \Rightarrow \ \ N_3=12$

$x = R_{130}(1\cdot 65\cdot 1 + 2\cdot 26 \cdot 2 + 3 \cdot 10 \cdot 12)=79$

This is not correct, as one can easily see with the second equation.

I can't find my mistake :/ what's wrong?

## 1 Answer

If you set $$26\cdot N_2 \equiv_5 1 \ \ \Rightarrow \ \ N_2=1 \\ 10\cdot N_3 \equiv_{13} 1 \ \ \Rightarrow \ \ N_3=4$$ Then you'll get the right number $$x = R_{130}(1\cdot M_1 \cdot N_1 + 2\cdot M_2 \cdot N_2 + 3 \cdot M_3 \cdot N_3)\\=R_{130}(1 \cdot 65\cdot 1 + 2\cdot 26 \cdot 2 + 3 \cdot 10 \cdot 12)\\ =R_{130}(65+52+120)=R_{130}(107)$$ This satisfies the question. $$107 \equiv_2 1, 107 \equiv_5 2, 107 \equiv_{13} 3$$

• ah, sure - it I'm looking for the inverse so it must be 1. Thanks – xotix Jan 14 '18 at 17:03