# The Chinese Remainder Theorem

## 21 thoughts on “The Chinese Remainder Theorem”

1. sudheer |

Can u explain how remainder of ((9^5)^402 )/11 is 1?

2. Sakshi |

hi,
Is it okay if we break 64 (divisor) in 4 and 16s.. Or it should be prime factors or co prime factor

3. Sakshi, the divisors should very definitely be co-prime to each other. Simplest way is to just split it into prime factors and their powers. So 24 could be split as 8 * 3 for example.

regards
J

4. Tarun Bagri |

Hi J,

Why do we write 17^21^23 as 17^6K + 5.
It has to be broken down as 4K+ … because the cyclicity of 7 is 4??

5. That is the cyclicity of last digits, Tarun – it has nothing to do with this question? We are discussing remainders….don’t confuse the two. Powers of 17 when divided by 13 repeat in 6 steps (as seen in an earlier question) and hence we took 6k +…

regards
J

I was wondering if the method will hold even if we have factors which are not co-primes.
So let’s say we have (21^1001)/120. If I write 120 = 12 * 10 , we will have two matching pattern with remainder 21 and 81 (Since LCM of 12,10 is 60). But if I write 120 = 24 * 5, I will get only one matching pattern with remainder 21 (since LCM equals divisor 120). Does that mean that wherever the factors are not co-primes, the first remainder will always be the correct one or is it not correct to use non co-primes factors while using this method.

• As far as I know, with non co-primes it might give the correct answer by chance but is not guaranteed to do so. So definitely a risk I wouldn’t advise! ðŸ™‚

regards
J

7. Sandipan |

suppose 15^400 divided by 1309(11*17*7) now can we apply CRT?

• Yes you can. But even a 2-step CRT hasn’t appeared in CAT so I think we may safely assume that a 3-step one will not show its face.

regards
J

8. CAT2015_aspirant |

Hello Sir

How do we write 17^(21^225) as 17^(6k+3)

Thanks a lot.

• 21^225 divided by 6 leaves 3 remainder (see earlier remainders posts to figure out how – actually any power of 21 will give 3 :P). So it is of the form 6k+3

regards
J

9. Renu |

Sir, for finding the remainder of ((3^10 -1)/2)/44. I have used 8 & 11 as two numbers for finding the remainder of the expression using chinese remainder theorem. From the 2 calculation, i got 0 in both the cases. So, is it implying that both the 11k+r1 & 8k+r2 are matching when k =0 with r’s zero too?? M i interpreting correctly?
Regards,

10. find the remainder of 11^30/34 ?

• Don’t bother. Out of scope for CAT (you could use Chinese remainder with 2 x 17, but really not worth the effort)

regards
J

11. how to fin remainder of 11^30/34 ?

12. cat2015 |

(25^6+5^126)/65 gives 80 remainder but answer shows 0? how is this possible J? Applied chinese remainder theorem

25^6+5^126 = 5^12 + 5^126 = 5^12(5^114+1)
Now 5^12 is divisible by 5.
Also 5^114 gives remainder 12 with 13 so 5^114 + 1 will be divisible by 13. Hence it is totally divisible by 65 and will give 0.
Do note that when dividing by 65, a remainder of 80 is anyway not possible. So you have made some seriously fundamental error even besides the CRT part ðŸ˜¦

regards
J

• cat2015 |

see individually if we see
5^12 / 13 gives remainder 1 (5*5/13=-1/13== -1^6 /13)
and 5^126 also gives the same remainder i.e 1
combining we get a remainder 2.
is this approach not ok?

13. How does 5^126 give you 1? It is (5^2)^63 = (-1)^63 = -1.

regards
J

14. cat2015 |

ohh yes!!! I made a silly mistake.
thank you J for the prompt replies (Y), otherwise i would have been left scratching my head.