Find an integer congruent to $1 \pmod{7}$ and to $2 \pmod{11}$.
Let's list the integers congruent to $2 \pmod{11}$ until we find one congruent to $1 \pmod{7}$. The sequence is $11k + 2 = 2, 13, 24, 35, 46, 57, \cdots$ for $k = 0, 1, 2, 3, 4, 5, \cdots$. They are congruent to: $2, 6, 3, 0, 4, 1, \cdots$. Therefore, 57 is the first number found to be congruent to $1 \pmod{7}$ and $2 \pmod{11}$.

This exercise generalizes to:

## Chinese Remainder Theorem

Let $a_{1}, a_{2}, \cdots, a_{n}$ be $n$ integers that are pairwise coprime, and $b_{1}, b_{2}, \cdots, b_{n}$ be any integers. The system of equations:

$$
\begin{array}{cc}
x \equiv b_{1} & \left(\bmod a_{1}\right) \\
x \equiv b_{2} & \left(\bmod a_{2}\right) \\
\ldots \\
x \equiv b_{n} & \left(\bmod a_{n}\right)
\end{array}
$$

admits an infinite number of solutions of the form $x \equiv B \left(\bmod a_{1} a_{2} \cdots a_{n}\right)$.

## Proof

Let $N = a_{1} a_{2} \cdots a_{n}$. Suppose there exists a solution $x = B$. Any other solution must be such that $x - B$ is divisible by $a_{1}, a_{2}, \cdots, a_{n}$, and thus by their product $N$ since these $n$ integers are pairwise coprime. Conversely, any $x \equiv B \pmod{N}$ is congruent to $B$ modulo each of the $a_{i}$, and thus is a solution to the system of equations. It remains to prove that there is at least one solution, by explicitly exhibiting one. Let $N_{i} = \frac{N}{a_{i}}$, the product of all the $a_{j}$ except one, $a_{i}$. $N_{i}$ is coprime with $a_{i}$, so by Bézout's identity there exist $x_{i}$ and $y_{i}$ such that $x_{i} N_{i} + y_{i} a_{i} = 1$, or $x_{i} N_{i} \equiv 1 \pmod{a_{i}}$, while for all other $a_{j}$, $x_{i} N_{i} \equiv 0 \pmod{a_{j}}$. Consequently, the sum $B = x_{1} N_{1} b_{1} + x_{2} N_{2} b_{2} + \cdots + x_{n} N_{n} b_{n}$ satisfies each congruence in the system.