The Chinese Remainder Theorem

The Chinese Remainder Theorem gives a method for solving simultaneous linear congruences of the form

Theorem (Chinese Remainder Theorem)

Letbe positive integers such thatforthen the system of linear congruenceshas a simultaneous solution which is unique

Proof:

Letand letforThen sincefor eachand so the linear congruencehas a unique solutionLet this solution besoand construct the number - we show this satisfies satisfies each of the congruences. To show this we evaluatefor eachWheneversince divideswe havehence for eachas each of the remaining terms in the sum is congruentto 0.

Sincewas found such thatwe have

We now show uniqueness. Supposeis a second solution of the system: This implies eachdivideswhereupon the fact that the moduli are relatively prime gives us thatdividessoas required.

Example: Solve the system of linear congruences

We have

We solve

Hence

Example: Solve the congruence

Since 1001=7*11*13 we seek the simultaneous solution ofor equivalently

Hence