Math & Physics Problems Wikia
Advertisement

Problem

The Chinese remainder problem is a system of linear modular congruences

where are mutually coprime.

Construct the solution to the Chinese remainder problem.

Sun Tzu Chinese remainder theorem.svg.png

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