New Batches at TathaGat Delhi & Noida!               Directions to CP centre
previous CAT question
by 50 cent - Friday, 22 June 2012, 04:36 PM
  31001 /1001
find the remainder
Re: previous CAT question
by Mohit Sharma - Friday, 22 June 2012, 04:53 PM
  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
by 50 cent - Tuesday, 26 June 2012, 05:21 PM
  no dear the ans is not that ............ its 971 .......... please post the method if u get this ans....
Re: previous CAT question
by AAKERSHIT GUPTA - Sunday, 1 July 2012, 10:11 PM
  1001 is not a prime number. it will be a product of 3 prime no's. 7 11 13
Re: previous CAT question
by AAKERSHIT GUPTA - Sunday, 1 July 2012, 10:27 PM
  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
by 50 cent - Monday, 16 July 2012, 08:54 PM
  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
by TG Team - Monday, 16 July 2012, 09:44 PM
 

Hi Siddharth smile

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

Re: previous CAT question
by babloo aggarwal - Sunday, 22 July 2012, 01:32 AM
  Is there another method besides fermat and chinese remainder theorem
Re: previous CAT question
by 50 cent - Monday, 23 July 2012, 10:29 AM
  Hi babloo,smile

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
by 50 cent - Sunday, 29 July 2012, 06:13 PM
  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
by TG Team - Tuesday, 31 July 2012, 06:54 AM
 

Hi Siddharth smile

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

Re: previous CAT question
by 50 cent - Wednesday, 1 August 2012, 10:02 PM
  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

Re: previous CAT question
by Harigaran Hari - Sunday, 28 June 2015, 09:27 PM
  how it comes
3^1001 / 7 ----> 3^5/7 , remainder - 5

3^1001/11 ----> 3/7 ,remainder - 3

3^1001/13 ----> 3^5/13 , remainder - 9
pls explain