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

Question

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?

Answer 1

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.

TL;DR: followed the method from the wikipedia page of the CRT

Answer 2

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.

Answer 3

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