## Solving simultaneous modular congruences

Let $\{n_i\}_{i=1}^k$ be a set of pairwise relatively prime integers- that is, $\mathsf{gcd}(n_i,n_j) = 1$ whenever $i \neq j$.

1. Show that the Chinese Remainder Theorem implies that for any $\{a_i\}_{i=1}^k \subseteq \mathbb{Z}$, there is a solution $x \in \mathbb{Z}$ to the simultaneous congruences $x \equiv a_i$ mod $n_i$ and this solution is unique mod $n = \prod n_i$.
2. Let $n_i^\prime = n/n_i$ for each $i$; note that $n_i^\prime$ and $n_i$ are relatively prime by assumption. Let $t_i$ be the inverse of $a_i^\prime$ mod $a_i$. Prove that the solution $x$ in part (a) is $x = \sum a_it_in_i^\prime$ mod $n$. (Note that these $t_i$ can be found quickly using the Euclidean Algorithm, and thus we can quickly find solutions to the system of congruences for any choice of the $a_i$.)
3. Solve the simultaneous system of congruences $x \equiv 1 \mod 8$, $x \equiv 2 \mod 25$, and $x \equiv 3 \mod 81$ and the system $y \equiv 5 \mod 8$, $y \equiv 12 \mod 25$, and $y \equiv 47 \mod 81$.

1. Since the $n_i$ are pairwise relatively prime, the ideals $(n_i)$ are pairwise comaximal. By the Chinese Remainder Theorem, the map $\varphi : \mathbb{Z} \rightarrow \prod \mathbb{Z}/(n_i)$ is surjective and has kernel $(\prod n_i)$. Consider the element $(\overline{a_i}) \in \prod \mathbb{Z}/(n_i)$; then there exists an element $x \in \mathbb{Z}$ such that $\varphi(x) = (\overline{x}) = (\overline{a_i})$. By the First Isomorphism Theorem for rings, $x$ is unique mod $n$.
2. It suffices to show that this $x$ is indeed a solution. To that end, consider $\varphi(x) = (\sum a_it_in_i^\prime)$. Note that the $j$th coordinate of $\varphi(x)$ is $\sum a_it_in_i^\prime$, taken mod $n_j$. By definition, $n_j$ divides $n_i^\prime$ for all $i \neq j$. Thus the $j$th coordinate of $\varphi(x)$ is $a_jt_jn_j^\prime \equiv a_j$, since $t_j$ is the inverse of $a_j^\prime$ mod $n_j$. Thus $\varphi(x) = (a_i)$ as desired.
3. For both of these examples, we have $n_1 = 8$, $n_2 = 25$, and $n_3 = 81$ (certainly these are pairwise relatively prime). Thus $n_1^\prime = 25 \cdot 81$, $n_2^\prime = 8 \cdot 81$, and $n_3^\prime = 8 \cdot 25$. We wish to invert $n_i^\prime$ mod $n_i$. Since $n_1^\prime \equiv 1$ mod 8, $t_1 = 1$. Since $n_2^\prime \equiv -2$ mod 25 and $25 - 2 \cdot 12 = 1$, $t_2 = 12$. Since $n_3^\prime \equiv 38$ mod 81 and $38\cdot 32 - 15 \cdot 81 = 1$, $t_3 = 32$.

Thus $x = \sum_{i=1}^3 a_i \cdot t_i \cdot n_i^\prime$ $= 1 \cdot 1 \cdot 25 \cdot 81 + 2 \cdot 12 \cdot 8 \cdot 81 + 3 \cdot 32 \cdot 8 \cdot 25$ $\equiv 4377$ mod $8 \cdot 25 \cdot 81$.

Similarly, $y \equiv 15437 \mod 8 \cdot 25 \cdot 81$.