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.

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.