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
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
Example: Solve the congruence
Since 1001=7*11*13 we seek the simultaneous solution ofor equivalently