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.