In this post, we will look at Chinese remainder theorem.
Let’s take a small example to begin with. Say we have to find the remainder of 1003 divided by 99.
Now, we can easily divide 1003 by 99 and get the remainder to be 13. However, let’s see if we can use some other method to solve this:
99 can be split as 9 and 11 where 9 and 11 are co-prime to each other. The remainder of 1003 divided by 9 will be 4 and so, we can write the original number in the form on 9a+4. Similarly, the remainder of 1003 divided by 11 will be 2 and so, we can write it as 11b+2 where a and b are integers. As we are representing the same number in two different forms, they would be equal to each other. So,
9a+4 = 11b+2 ……… (original equation)
9a = 11b – 2
Now, we have a linear equation with 2 variables. So, it will have infinite integral solutions. We take ‘any’ of the possible solutions and proceed. To start with, we generally put a variable as 0 and then start the iterations. Let’s say, b = 0. But then a will not be an integer. Similarly, we try out for for b = 1 and voila! we get a = 1 and subsequently both a and b as integers. So, a = 1, b = 1 is definitely a solution. We simply substitute the value of a or b back into the original equation and get our remainder to be 13.
So, to sum it up and extend it to questions involving higher powers, when a^n mod b is given such that a and b are co prime and b can be expressed as a product of two prime numbers m and p, you can find individual remainders for division of a^n by m and p and then equate the two. Such that mx+c=ny+d where c and d are remainders obtained through calculation. Let’s look at this example:
9^2013 mod 77 = ?
9^2013 mod 7 and 9^2013 mod 11
2^2013 mod 7 and -2^2013 mod 11
8 mod 7 and 36 mod 11
7a+1 = 11b+3
7a-11b=2 => 7a=2+11b => 11b gives remainder of 5 => b=1; r=4; b=2, r=1, b=3, r=5 …
Number is 36
7^6666 mod 65
7^6666 mod 13 and 7^6666 mod 5
7^6 mod 13 and 2^6666 mod 5
13a+12 and 5b+4
5b=8+13a => 13a should leave remainder of 2. a=1, r=3, a=2, r=1, a=3, r=4, a=4, r=2
So, number is 64.
Go through the following videos to understand the concept behind Chinese remainder theorem and look at solved examples.
This article first appeared as 18 days to CAT 2015 under the series 75 days to CAT 2015.