1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$$

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

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.