Chinese Remainder Theorem

Chinese Remainder Theorem

Statement

Constructive Proof

Example

Solve:

, ,

(since ) (since ) (since )

Ring Isomorphism

Generalization

Applications

Example: Computing

(coprime factors)

(obvious)

(since )

By Fermat: , so

CRT: ,

Gaussian Integers

Historical Note

The theorem dates to Sun Tzu's "Sunzi Suanjing" (3rd century CE), making it one of the oldest results in number theory.