# Calculate all numbers $x ∈ ℤ$ that simultaneously satisfy the following 3 congruences

Calculate all numbers $$x ∈ ℤ$$ that simultaneously satisfy the following 3 congruences:

$$x ≡ 7 mod 11$$

$$x ≡ 1 mod 5$$

$$x ≡ 18 mod 21$$

How can I solve this system for $$x$$? I've tried the chinese remainder theorem, but i dont get the part with the modulo inverse. I know there must be a solution like $$x = n+1155k$$ with $$k ∈ ℤ$$, how i get the $$n$$? Any hints of solutions are greatly appreciated. What value of x satisfies these three equations?

• Try by substitution it since $x=5k+1$ use it in the other congruences
– user795628
Jan 26, 2021 at 13:12

We first look for a non-trivial solution of the system

\begin{align*} &x \equiv 1 \mod 11\\ &x \equiv 1 \mod 5\\ &x \equiv 1 \mod 21 \end{align*}

We have $$5 \times 21 = 105$$, coprime with $$11$$. Hence, we can find $$a_1, b_1 \in \mathbb Z$$ such that $$11 a_1 + 105b_1 = 1$$. Using your favourite algorithm (for example, one adapted from the Euclide GCD algorithm) you find

$$11\times(-19) + 105 \times 2 = 1$$.

We repeat this process for the other equations:

$$11 \times 21 = 231$$ and

$$5 \times (-46) + 231 \times 1 = 1$$

And for the final equation,

$$11 \times 5 = 55$$ and

$$21 \times 21 + 55 \times (-8) = 1$$

We have computed some interesting things, but what was the point of all that ? Well, if you look carefully at what we have just done, you notice that the first Bezout relation that we computed tells us that $$105 \times 2 = 210 \equiv 1 \mod 11$$. Moreover, because $$105 = 5 \times 21$$, we automatically have that $$210 \equiv 0 \mod 21$$ and $$210 \equiv 0 \mod 5$$.

Combining those results, we have:

$$7 \times 210 \equiv 7 \mod 11$$ and is equal to $$0 \mod 5$$ and $$\mod 21$$

$$1 \times 231 \equiv 1 \mod 5$$ and is equal to $$0 \mod 11$$ and $$\mod 21$$

$$18 \times 55 \times (-8) \equiv 18 \mod 21$$ and is equal to $$0 \mod 5$$ and $$\mod 11$$

We compute the sum of those three number:

$$x = 7 \times 210 + 1 \times 231 + 18 \times 55 \times (-8) = -6219$$

We can "get this number back" in a more appropriate range:

$$-6219 \equiv -6219 + (6\times 1155) \equiv 711 \mod 1155$$

Everything we have done shows that $$711$$ is a solution to your initial system.

If $$x \equiv 7\pmod {11}$$, then $$x = 11p + 7$$ for some integer $$p$$. Then, we have:

$$11p + 7\equiv 1\pmod 5$$

$$p \equiv 4\pmod 5$$

Thus, $$p = 5q + 4$$ for some integer $$q$$. Then:

$$x = 11p + 7$$

$$x = 11(5q + 4) + 7$$

$$x = 55q + 51$$

Substituting into the last congruence:

$$55q + 51\equiv 18\pmod{21}$$

$$13q\equiv 9\pmod{21}$$

Note that $$13^{-1}\equiv 13\pmod{21}$$:

$$q\equiv 117\pmod{21}$$

$$q\equiv 12\pmod{21}$$

Then, $$q = 21r + 12$$ for some integer $$r$$:

$$x = 55(21r + 12) + 51$$

$$\boxed{x = 1155r + 711\text{ for }r\in\mathbb{Z}}$$

This strategy will work with any number of congruences. The only real work here is finding modular inverses.

We must have $$x=18+21k\qquad k\in\mathbb{Z}.$$ Then the congruence modulo $$11$$ becomes $$x\equiv7+10k\equiv7\bmod 11$$ so that $$k=11\ell$$ wth $$k\in\mathbb{Z}$$. Considering now the congruence modulo $$5$$ we get $$x\equiv18+21\cdot11\ell\equiv3+\ell\equiv1\bmod 5,$$ i.e. $$\ell\equiv3\bmod5$$.

Thus take $$\ell=3$$, hence $$k=33$$ and finally $$x=18+21\cdot33=711$$.