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)

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