Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) allows us to solve systems of congruences with coprime moduli. It bridges local properties (modulo $p$ ) to global properties (modulo $N$ ).

Statement

Theorem (Chinese Remainder Theorem)

Let

n_{1}, n_{2}, \dots, n_{k}

be pairwise coprime positive integers. Let

N = n_{1} n_{2} \dots n_{k}

. For any integers

a_{1}, a_{2}, \dots, a_{k}

, the system of congruences:

x \equiv a_{1} (mod n_{1})

x \equiv a_{2} (mod n_{2})

⋮

x \equiv a_{k} (mod n_{k})

has a solution

x

, and this solution is unique modulo $N$ .

Construction Algorithm

To find

x

Let $N_{i} = N / n_{i}$ .
Find the modular inverse $y_{i}$ of $N_{i}$ modulo $n_{i}$ (i.e., $N_{i} y_{i} \equiv 1 (mod n_{i})$ ).
The solution is:

x = i = 1 \sum k a_{i} N_{i} y_{i} (mod N)

Garner's Algorithm

An alternative method useful for computer implementation, solving two at a time iteratively.

Practice Problems

Exercise (Problem 1)

Find the smallest positive integer

x

such that:

x \equiv 2 (mod 3)

x \equiv 3 (mod 5)

x \equiv 2 (mod 7)

Exercise (Problem 2)

Solve the system

x \equiv 1 (mod 4)

and

x \equiv 2 (mod 6)

. (Be careful: Moduli not coprime!).

Exercise (Problem 3)

A number leaves a remainder of 1 when divided by 2, 3, 4, 5, and 6. What is the smallest such number greater than 1?