How do I solve the system of congruences $x \equiv 1 \pmod{3}$, $x \equiv 2 \pmod{4}$, $x \equiv 4 \pmod{5}$, $x \equiv 2 \pmod{7}$?

Question

Sorry for the weird title, but I don't know how else to phrase this.

Say I have a set of numbers, and the remainders each get by dividing them by a certain number. For instance:

$x \equiv 1 \pmod{3}$

$x \equiv 2 \pmod{4}$

$x \equiv 4 \pmod{5}$

$x \equiv 2 \pmod{7}$

I know the math is similar to finding the least common multiple, but I can't grok it. How do I find $x$ in the above equations, assuming they all use the same $x$?

Additionally, after that's found, how do I find further multiples that fit these restrictions?

Answer 1

You can use the Chinese Remainder theorem for this. (By the way, you should write "(mod $m$)" at the end of each line rather than in the middle.)

Conventionally, you write:

$x ≡ n$ (mod $m$)

https://en.wikipedia.org/wiki/Chinese_remainder_theorem

On the other hand, if there are a small number of a congruences to be solved, you can solve the congruences intuitively (which is actually the method from which the Chinese remainder theorem is derived):

$x ≡ 1$ (mod 3)

$x ≡ 2$ (mod 4)

$x ≡ 4$ (mod 5)

$x ≡ 2$ (mod 7)

Consider the first congruence: $x ≡ 1$ (mod 3).

The smallest $x$ which satisfies this is 1.

Next consider $x ≡ 2$ (mod 4). If you add multiples of 3 to 1, then the 1st congruence will still be satisfied. So keep adding 3 until you find an $x$ which satisfies $x ≡ 2$ (mod 4):

1, 4, 7, 10

Next consider $x ≡ 4$ (mod 5). If you add multiples of the LCM of 3 and 4 (12), the first 2 congruences will still be satisfied.

After the first 3 congruences are satisfied, start adding multiples of the LCM of 3, 4 and 7 until the fourth is satisfied too.

Repeat this method until you find the solution for all of the congruences (note that when you add multiples of the LCM, you may not need to add any at all (in other words add it 0 times), as the congruence you are considering may already be satisfied).

This method will definitely work if all of the modulos in the congruences are coprime (as there is always a solution if this is the case).

When you get $x$ from applying this method, if you add any multiple of the LCM of 3, 4, 5 and 7, the 4 congruences will still be satisfied. So the solution would be:

$x$ (mod $\operatorname{lcm}(3, 4, 5, 7)$)

Answer 2

Since $x\equiv2\pmod{4}$ and $x\equiv2\pmod{7}$, we must have that $x\equiv2\pmod{28}$.

We can use the Extended Euclidean Algorithm as implemented in this answer to solve the following equivalences.

Since $140=5\cdot28$, solve $$ \begin{align} x&\equiv1\pmod{3}\\ x&\equiv0\pmod{140} \end{align} $$ getting $x\equiv280\pmod{420}$.

Since $84=3\cdot28$, solve $$ \begin{align} x&\equiv1\pmod{5}\\ x&\equiv0\pmod{84} \end{align} $$ getting $x\equiv336\pmod{420}$.

Since $15=3\cdot5$, solve $$ \begin{align} x&\equiv1\pmod{28}\\ x&\equiv0\pmod{15} \end{align} $$ getting $x\equiv225\pmod{420}$.

We can get the solution to the original equivalence as $$ x\equiv\overbrace{1\cdot280}^{\substack{1\pmod{3}\\0\pmod{4}\\0\pmod{5}\\0\pmod{7}}}+\overbrace{4\cdot336}^{\substack{0\pmod{3}\\0\pmod{4}\\4\pmod{5}\\0\pmod{7}}}+\overbrace{2\cdot225}^{\substack{0\pmod{3}\\2\pmod{4}\\0\pmod{5}\\2\pmod{7}}}\equiv\overbrace{\ 394\ }^{\substack{1\pmod{3}\\2\pmod{4}\\4\pmod{5}\\2\pmod{7}}}\pmod{420} $$

Answer 3

This is known as the Chinese Remainder Theorem. https://en.wikipedia.org/wiki/Chinese_remainder_theorem

This page describes the general solution method.