Solving simple system of congruences

Question

I have this example from wikipedia:

$$x \equiv 3 \pmod 4$$ $$x \equiv 4 \pmod 5$$

$$x = 4a + 3\\ 4a + 3 \equiv 4 \pmod 5\\ 4a \equiv 1 \equiv -4 \pmod 5\\ a \equiv -1 \pmod 5\\ x = 4(5b - 1) + 3 = 20b - 1 $$

But wikipedia shows $20b + 19$...what did I do wrong here?

You have done everything right. $N \equiv -1 \equiv 19 (\mod 20)$ — Inceptio, May 22 '13 at 14:35

Key Ideas · Accepted Answer · 2013-05-22T14:52:21.653

1

Your answer is equivalent since $\ 19 \equiv -1\pmod{20}.\ $ Explicitly $\ 20b\!+\!19 = 20(b\!+\!1)\!-\!1.\,$

Simpler: $\, x \equiv -1\, $ mod $\,4,5\ \Rightarrow\ x\equiv -1\,$ mod $\,{\rm lcm}(4,5) = 20,\ $ i.e. $\ 4,5\mid x\!-\!1\,\Rightarrow\, 4\cdot 5\mid x\!-\!1.$

edited May 22 '13 at 14:52

answered May 22 '13 at 14:40

Key Ideas

4,224

Is there a faster way to solve such systems, in case I had more equations? – khernik May 22 '13 at 14:43
The above is one optimization of the Chinese Remainder Theorem (CRT). It often proves handy for small numbers. In general you need to resort to CRT, computing inverses by the extended Euclidean algorithm (or some equivalent). – Key Ideas May 22 '13 at 14:46

score 0 · Answer 2 · answered May 22 '13 at 14:46

0

Generalization:

$a \equiv b(\mod n)$ if $b<n$, $a\equiv b-n (\mod n)$

The reason is quite simple, $a \equiv b-n (\mod n) \implies a+n \equiv b(\mod n)$

answered May 22 '13 at 14:46

Inceptio

7,881

Solving simple system of congruences

2 Answers2