In this post I would like to talk about the Chinese Remainder Theorem. You might have heard this problem as a kid: There are x number of things. When taken in groups of 5, they leave a remainder 1. When taken in groups of 7, they leave a remainder 2. When taken in groups of 9, they leave a remainder 3. And when taken in groups of 11, they leave a remainder 4. Find the value of x. We will see how such problems can be solved using the Chinese Remainder Theorem(CRT). LINEAR CONGRUENCES Lets talk about linear congruences. You might have already encountered them informally in my previous post on the RSA encryption system. Here I would like to introduce it a bit more formally. ax ≡ b (mod n) Abusing the use of notation, we can express this equation into a form which might look more familiar, i.e ax%n = b. In other words, the integer ax when divided by n leaves a remainder equal to b. Lets say that we find a solution to the above equation, say x = x 0 . => ax 0 ≡ b (...