Chinese remainder theorem

The Chinese remainder theorem states that given a set of pairwise co-prime numbers ${𝑝 1, 𝑝 2, \dots, 𝑝 𝑛}$ with a product $𝑀 = \prod 𝑛 𝑖 = 1 𝑝 𝑖$ , then the following set of congruence equations

𝑥 \equiv 𝑝 1 𝑎 1 𝑥 \equiv 𝑝 2 𝑎 2 ⋮ 𝑥 \equiv 𝑝 𝑛 𝑎 3

is guaranteed a solution, unique up to congruence modulo $𝑀$ .

Solution

For $𝑖 = 1, 2, \dots, 𝑛$ , define $𝑏 𝑖$ so that

𝑏 𝑖 (𝑀 𝑝 𝑖) \equiv 𝑝 𝑖 1

which is guaranteed to exist by Bézout's lemma and the co-prime requirement, then the value of $𝑥$ is given by

𝑥 \equiv 𝑀 𝑛 \sum 𝑖 = 1 𝑎 𝑖 𝑏 𝑖 (𝑀 𝑝 𝑖)

This works since every term except the $𝑖$ -th term goes to $0$ modular $𝑝 𝑖$ , and thus

𝑥 \equiv 𝑝 𝑖 𝑎 𝑖 𝑏 𝑖 (𝑀 𝑝 𝑖) \equiv 𝑝 𝑖 𝑎 𝑖 \cdot 1 \equiv 𝑎 𝑖

This is generalized by the Chinese remainder theorem for rings

Practice problems

Mary Radcliffe, Chinese Remainder Theorem (examples)

#state/tidy | #lang/en | #SemBr | #review