21 thoughts on “The Chinese Remainder Theorem

  1. 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

  2. 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

  3. 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

  4. 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,

    • Answer should be 0.
      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

      • 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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s