Advertisement
349
pages

## Problem

The Chinese remainder problem is a system of linear modular congruences

where are mutually coprime.

Construct the solution to the Chinese remainder problem.

## Solution

We begin with the system of linear congruences:

where are mutually coprime.

Let and .

From this consturction, shares no factors with ; therefore,

and when .

Let be the modular inverses of respectively. By the property of modular inverses,

.

Consequently

.

Since whenever , it follows that .

Consequently, the sum satisfies all linear congruences in the original system, and the complete solution is

.

## Historical Note

Sun Zi was an obscure Chinese mathematician who flourished sometime during the 3rd - 5th century AD. He authored the Sunzi Suanjing (Master Sun's Computational Canon).

Advertisement