Chinese remainder theorem
A certain number x is divided by 3 and a remainder of 2 results. The same number x is divided by 5 and a remainder 4 results.
The same number x is divided
by 7 and a remainder of 3 results. What is this number x ?
This is the famous Chinese remainder theorem.
Following is my own unique method for solving this puzzle.
Let the dividers all be prime.
Let x be the number we are looking for.So for n dividers and n remainders we have:
x == a1 mod p1 (equation 1)
x == a2 mod p2 (equation 2)
x == a3 mod p3 (equation 3)
x == a4 mod p4 (equation 4)
.
.
.
x == an mod pn (equation n)
Now we start by multiplying equation 1 by p2 and equation 2 by p1
We then have x p2 == a1 p2 mod( p1 p2) and
x p1 == a2 p1 mod( p2 p1)
But GCD(p2, p1) =1 , so we can find a r and s so that rp2 + sp1 = 1
Therefore we have xrp2 == ra1 p2 mod( p1 p2) and
xsp1 == sa2 p1 mod( p2 p1) and thus
xrp2 + xsp1 == ra1 p2 + sa2 p1 mod( p1 p2)
So x == ra1 p2 + sa2 p1 mod( p1 p2)
So x == b2mod ( p1 p2) where b2= ra1 p2 + sa2 p1
Next we look at x == b2mod ( p1 p2) and x == a3 mod p3
We do the same as above and get x == b3mod ( p1 p2 p3)
In the end we will have x == bnmod ( p1 p2 p3.....pn)
So x = bn will then be the number we are looking for.
Example:
x == 2 mod 3 , x == 4 mod 5 , x == 3 mod 7
We look at x==2 mod 3 and x == 4 mod 5 first
So we have 5x == 10 mod 15 and 3x == 12 mod 15 following our algorithm
We multiply to get a difference of 1 between the coeficients of the x'e
So we have 10x == 20 mod 15 and 9x == 36 mod 15
Next we subtract and are left with x == -16 mod 15, so x == -1 mod 15
Next we look at x == -1 mod 15 and x== 3 mod 7
So 7x == -7 mod 105 and 15x == 45 mod 105
So 14x == -14 mod 105 and 15x == 45 mod 105
So x == 59 mod 105
Therefore x = 59 and we see indeed that 59/3 has a remainder of 2, 59/5 has a remainder of 4 and 59/7 has a remainder of 4