 |
You are here,
 |
 | previous CAT question |
|
31001 /1001 find the remainder |
| Re: previous CAT question |
|
Hi siddharth, Its simple, as 3 and 1001 are co primes. According to Fermat's Theorem, a^p/p=a where a and p are co primes. Hence, ans is 3. Thanks |
| Re: previous CAT question |
| no dear the ans is not that ............ its 971 .......... please post the method if u get this ans.... |
| Re: previous CAT question |
| 1001 is not a prime number. it will be a product of 3 prime no's. 7 11 13 |
| Re: previous CAT question |
|
hi.. this is a good one. see when we use fermite theorem then what is left is 3^281/1001. Now 3^10 is 59049(This one was lengthy). so the remainder will come out to be 10 by this. now we can write 3^281 will be 10^28*3/1001. so the next step will be 10^3 will be 1000. we can write this 1000^9*10*3/1001. 100 will give a remainder of -1. so the final statement left with us is -30/1001. hence the remainder will be 1001-30 = 971. phew! thanks got it? |
| Re: previous CAT question |
| ya got it.. but is there another method than this one because it is very much time consuming. Please post if have a smaller method |
 | Re: previous CAT question |
|
Hi Siddharth You can use Chinese remainder Theorem also. As 1001 = 7*11*13, so find individual remainders and then combine them. If options are available then there is no need to combine different remainders. You just need to check the options then. 31001 = (36)166*35 = 35 mod7 = 5 mod7 as 36 = 1 mod7 31001 = (35)200*3 = 3 mod11 as 35 = 1 mod11 31001 = (33)333*32 = 9 mod13 as 33 = 1 mod13 Now you can easily check the options which satisy all the three conditions. |
| Re: previous CAT question |
| Is there another method besides fermat and chinese remainder theorem |
| Re: previous CAT question |
Hi babloo, First of all 1001 has factor 7, 11 , 13 now, 3^1001 / 7 ----> 3^5/7 , remainder - 5 3^1001/11 ----> 3/7 ,remainder - 3 3^1001/13 ----> 3^5/13 , remainder - 9 so we get 7a + 5 = 11b + 3 = 13c+9 now what is word interpretation of the above statement .. find the smallest number which when divided by 7 gives remainder 5 , when divided by 11 leaves remainder 3 and when divided by 13 leaves remainder 9? first take any two condition , i always prefer big numbers 11b + 3 = 13c + 9 divisor of 13 + 9 = 9,22,35,48,61,74,87,100,113,126,139 divisor of 11 + 3 - 3,14,25,36,47,58,69,80,91,102,113 so smallest number is 113 whats the next number then ? its of form LCM(11,13) + 113 = 143k + 113 so we have combined two conditions so now our job is to compare this with third one 143k + 113 = 7a + 5 143k + 108 = 7a 140+ 3k + 105 + 3 = 7a so 3k + 3 should give 0 remainder when divided by 7 so k = 6 final remainder is hence 143(6) + 113 = 971  |
| Re: previous CAT question |
|
kamal sir, I didnt understand how you did the sum with Chinese theorem. Please explain how to apply it to every sum. |
| Re: previous CAT question |
|
Hi Siddharth CRT is to just combine remainders obtained by different co-prime divisors. i.e. Let's say N = 77Q + R Now when N is divided by 7, remainder obtained will be same as if would be obtained by dividing R by7. Same goes with 11 also. So just calculate the remainders by co-prime divisors of the number and check the options for R as R should be a number which gives same remainder from the divisors as given by N. Please try to grasp, what I have said. And better is to write the equation on your own and check my words. |
| Re: previous CAT question |
|
ok sir bt the way u did in the modulus way... U said that seeing the options v cn get d ans.. Bt i didnt understand how u did n arranged in that modulus method and how combining the 3 equation v can get d ans i.e, 971 Thanku |
