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}\).

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)).\]

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}\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用