Chinese Remainder Theorem

Chinese Remainder Theorem (CRT)

Theorem

For all integers and , and positive integers and , if , then the simultaneous linear congruences:

Have a unique solution modulo .

Thus, if is one particular solution, then the solutions are given by the set of all integers such that

(See GCD)

Proof

Let and be arbitrary integers, and and be arbitrary positive integers.
Assume that .
From the definitions of congruence and divisibility, the set of solutions to the congruence is given by:

Now we have , and hence from linear congruence theorem (with ) and the definitions of congruence and divisibility, the set of solutions to the above linear congruence is given by

where is one particular solution (which must exist).
Hence replacing with in (1), the set of solutions to the simultaneous congruences is given by:

You can't use 'macro parameter character #' in math mode\{m_1(m_2 y + x_0) + a_1 \mid y \in \Z\} = \{m_1 m_2 y + (m_1 x_0 + a_1) \mid y \in \Z\}$$ which is simply the congruence class $[n_0]$ in $\Z_{m_1 m_2}$, where $n_0 = m_1 x_0 + a_1$ is one particular solution. $$\QED

Generalized Chinese Remainder Theorem (GCRT)

Theorem

For all positive integers and , and integers , if for all , then the simultaneous congruences

have a unique solution modulo .
Thus, if is one particular solution, then the solutions are given by the set of all integers such that

Examples

Example

Solve the simultaneous congruences

Since , we can use the Chinese remainder theorem, which says that the solution to these simultaneous congruences is the set of all integers such that , where is one particular solution.

Note that are the choices of integers between and that are congruent to
Now observe that , , and , so is a solution to both congruences simultaneously.

We conclude that the set of solutions to the simultaneous congruences consists of all integers such that