Number theory MOC

Chinese remainder theorem

The Chinese remainder theorem states that given a set of pairwise co-prime numbers with a product , then the following set of congruence equations

is guaranteed a solution, unique up to congruence modulo .

Solution

For , define so that

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

This works since every term except the -th term goes to modular , and thus

This is generalized by the Chinese remainder theorem for rings

Practice problems

• Mary Radcliffe, Chinese Remainder Theorem (examples)

---

tidy | en | sembr | review