Based in Maryland, Mathwizurd.com is REVOLUTIONIZINg the world, one post at a time. With topics ranging from Biology to Multivariable Calculus, this website covers the entire academic spectrum.

Chinese Remainder Theorem

Let's say you have this problem:

x%2 = 1
x%3 = 2
x%5 = 1

An easy way to do this is called the Chinese Remainder Theorem.

The first thing you want to do is split it up into %2, %3, and %5.

x = a + b + c
You want to make sure that only the first part (%2) is non-zero, because that simplifies it a lot, so x becomes:
_ + 2 * _ + 2 * _

You want to repeat this for 3 and 5, so it becomes

x = 3(5)_ + 2(5)_ + 2(3)_
 

The purpose of doing that is when you do x%5, x becomes 2(3)_ %5. We want x%5 to equal 1, so 6 * _ %5 should equal 1, and 6%5 already equals 1, so that specific _ is 1.

Now, x = 3(5)_ + 2(5)_ + 6

x%3 = 10_%3 = 2, and 10%3 = 1, so we have to multiply 10 * 2, so that x%3 = 2. So the _ is 2.

Now, x = 3(5)_ + 20 + 6

We now want x%2 to be equal to 1, and 15%2 already equals one, so that _ equals 1.

Now, x = 15 + 20 + 6 = 41.

This isn't the only number though, as when you add (or subtract) the lcm(2,3,5) = 30, you get a value that also works. The reason that works is when you split up the 41 + 30n, 30n%2 = 0, and 30n%3 = 0, and 30n%5 = 0, so when you perform x%5, the 30n is eliminated. 

So, we have our final answer:

x = 41 ± 30n

x = 11, 41, 71, 101, 131, ...



David Witten

Path Problems

Simon's Favorite Factoring Trick