# Chinese remainder theorem - A, B and C think of a code

A, B and C are trying to think of a code. A remembers that after dividing by 13, the residue is 8. its double increased by 1234 after dividing by 17 leaves us residue of 7. C remembers that its triple increased by 4321 after dividing by 19 gives residue of 6.

I've put together the following congruences:

x = 8 (mod 13)

2x + 1234 = 7 (mod 17)

3x + 4321 = 6 (mod 19).

Using the formulas: $x = x_0 + k(\dfrac{m}{gcd(a, m)})$, whereas $ax_0 + my_0 = b$. I've come to this:

x = 8 mod 13

x = 10 mod 17

x = 7 mod 19.

After that I've used Chinese Remainder theorem.

M1 = 323; x1 = 6; M2 = 247; x2 = 2; M3=221; x3 = 8.

I get 32820 mod 4199 = 3427 + 4199*k

The result is supposed to be 6586, but I fail to produce it. Can someone please tell me where the mistake is?

• Something is wonky with your formulas; you should have $x \equiv 7 \bmod 17$ and $x \equiv 12 \bmod 19$ (you can test these directly). Also, I assume "mod 14" is a simple type. Aug 17, 2018 at 14:51
• That formula you are using is for when you have a linear modular equation with two variables, $x$ and $y$, and want to generate all solutions from one of the solutions $x_0, y_0$. That is irrelevant here. Each of your modular equations has only one variable, that you need to isolate. For example, modulo $17$ you have $2x+1234=7\implies 2x=7-1234\equiv 14 \implies x=7$. Aug 17, 2018 at 15:05
• What about the second case? 3x + 4321 = 6 (mod 19). (6 - 4321) mod 19 = 17; 17 / 3? How do I get 12? Aug 17, 2018 at 16:07