The Chinese Remainder Theorem:

The Chinese Remainder Theorem: is a result of congruences in number theory and some aspects of abstract algebra. It was first published in the 3rd to 5th centuries by Chinese mathematician Sun Tzu. 

The Chinese Remainder Theorem: says if m (one) and m (two) are relatively prime then the system of congruences 

has a unique solution mod m (one) m (two). 

"max" + "may"= 

Example: Find the unique solution to the following congruences: 

so, now we assign all the letters to a specific number,

since (11,9) =1, then there exists x and y so that 

11x+9y=1

using Euclid's formula: we see that 11(5) + 9(-6) = 1

so by this formula we see that x=5 and y= -6. 

Now we will use the "max" + "may" formula: 

=11(2)(5)+ 9(6)(-6)

=  110 - 324

= -214

therefore N=83. 

Example: Find the unique solution to the following congruences: 

so now we assign the letters to a specific number, 

since (5,3) =1 then there exists x and y so that

5x + 3y =1

using Euclid's formula: we see that 5(2) + 3(-3) =1

so by this formula we see that x=2 and y=-3. 

Now we will use the "max"+ " may" formula: 

= 5(2)(2) + 3(3)(-3)

= 20 + -27

= -7

therefore N = 8

Quiz Question: Find the unique solution to the following congruences: 

using the chinese remainder theorem and the "max" + "min" formula. 

.

Credit due to: wikipedia and my class notes