Select Page

In this post, we will look at Chinese remainder theorem.

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 …

a=5, b=3

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-13a=8

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.

Part 1

Part 2

You can read the entire 75 days to CAT 2015 by clicking here.