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.