31.5 The Chinese remainder theorem

31.5-1

Find all solutions to the equations $x \equiv 4 \pmod 5$ and $x \equiv 5 \pmod{11}$.

$$ \begin{aligned} m_1 & = 11, m_2 = 5. \\ m_1^{-1} & = 1, m_2^{-1} = 9. \\ c_1 & = 11, c_2 = 45. \\ a & = (c_1 \cdot a_1 + c_2 \cdot a_2) \mod (n_1 \cdot n_2) \\ & = (11 \cdot 4 + 45 \cdot 5) \mod 55 = 49. \end{aligned} $$

31.5-2

Find all integers $x$ that leave remainders $1$, $2$, $3$ when divided by $9$, $8$, $7$ respectively.

$10 + 504i$, $i \in \mathbb Z$.

31.5-3

Argue that, under the definitions of Theorem 31.27, if $\gcd(a, n) = 1$, then

$$(a^{-1} \mod n) \leftrightarrow ((a_1^{-1} \mod n_1), (a_2^{-1} \mod n_2), \ldots, (a_k^{-1} \mod n_k)).$$

$$\gcd(a, n) = 1 \rightarrow \gcd(a, n_i) = 1.$$

31.5-4

Under the definitions of Theorem 31.27, prove that for any polynomial $f$, the number of roots of the equation $f(x) \equiv 0 (\mod n)$ equals the product of the number of roots of each of the equations

$$f(x) \equiv 0 \pmod{n_1}, f(x) \equiv 0 \pmod{n_2}, \ldots, f(x) \equiv 0 \pmod{n_k}.$$

Based on $\text{31.28}$–$\text{31.30}$.