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.
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 +…
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! 🙂
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
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 😦
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?
How does 5^126 give you 1? It is (5^2)^63 = (-1)^63 = -1.
CAT-holics 
Can u explain how remainder of ((9^5)^402 )/11 is 1?
Sudheer, it has been explained in the previous posts on remainders:
https://crackthecat.wordpress.com/2013/03/05/remainders-of-powers/
https://crackthecat.wordpress.com/2013/03/06/the-concept-of-a-negative-remainder/
https://crackthecat.wordpress.com/2013/03/07/applying-negative-remainders/
regards
J
hi,
Is it okay if we break 64 (divisor) in 4 and 16s.. Or it should be prime factors or co prime factor
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
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??
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
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
Hello Sir
How do we write 17^(21^225) as 17^(6k+3)
Can you please elaborate?
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
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,
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
how to fin remainder of 11^30/34 ?
(25^6+5^126)/65 gives 80 remainder but answer shows 0? how is this possible J? Applied chinese remainder theorem
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?
How does 5^126 give you 1? It is (5^2)^63 = (-1)^63 = -1.
regards
J
ohh yes!!! I made a silly mistake.
thank you J for the prompt replies (Y), otherwise i would have been left scratching my head.