New Batches at TathaGat Delhi & Noida!               Directions to CP centre
Remainders
by Software Engineer - Monday, 31 August 2009, 09:25 PM
  cat 2009 cat 2010 numbers remainders how to find remaindersIt is uncanny how children pick up a lot of small habits and beliefs of their parents. Even the ones that rebel against their parents bear subconscious resemblance to their father or mother. There is a lesson for instructors in this. It is important for them to realize that students mirror their feelings about CAT. If the instructor expresses or feels that CAT is tough, or is fearful about CAT, his students will mirror the same feeling and will be less confident. If the instructor is brazen and casual about the paper and scoffs the competition, his students would reflect the same feelings. Also, it is so necessary to have unflinching faith in one’s students. I still remember that during my school days my mother used to proudly proclaim that I was an intelligent kid. I was barely scrapping passing marks in the school exams. If truth be told I was at the bottom of the class, but my mother had her blinkers on. And because of my mother I also believed that I was second to none. It was only years later, during my boards exams, that I took to studying seriously, and managed to outperform everyone else. I don’t know if it was my mother’s blind love for me or that she could see some bright spark in me that made her claim my intelligence but it really had great effect on my attitude. And attitude, in an exam like CAT, is everything.

While I am trying to write a DI lesson for the CAT CBT Club, here is another sparkling gem produced by a TGite already famous amongst you all- Software Engineer. When I saw the sheer size of the article I was awed. And so will you all be. The hard work demands applause from all of you. So read the article guys and do not forget to thank Software Engineer for this one. - Total Gadha

remainders 1

remainders 2

remainders 3

remainders 4

remainders 5

remainders 6

remainders 7

remainders 8

Join our CBT Club for further discussions. We shall cover some problems based on this in the CBT Club this week.

 

If you think this article was useful, help others by sharing it with your friends!


Bookmark and Share
Re: Remainders
by AsHwIn Drmz - Monday, 31 August 2009, 09:29 PM
  Mind blowing article...Thx a ton SE Bhai...
Keep rockin

Ashwin
Re: Remainders
by ravikanth musti - Monday, 31 August 2009, 09:34 PM
  The patience has been rewarded!!!

Once again a master piece!


Re: Remainders
by hemant bhardwaj - Monday, 31 August 2009, 09:36 PM
  Whoa ........
Such a compact article ......
Well if u divide this article, remainder will be 0 ...... it covers all, nothing left......
Gud work....
Re: Remainders
by amit jain - Monday, 31 August 2009, 09:58 PM
  vowsmile.........  Thanks a lot.
Re: Remainders
by Arvind Kumar - Monday, 31 August 2009, 10:56 PM
  This is really a fantastic effort to help bell the CAT.
Thanks S.E.Bhai
Re: Remainders
by santhana lakshmanan - Tuesday, 1 September 2009, 12:08 AM
  That it has taken TG sir 3 days to read and approve this article speaks volumes about this "gem of an article".
Will update my grey cells thanking SE and TG all the time.
Re: Remainders
by ishaan sharma - Tuesday, 1 September 2009, 01:16 AM
  A piece of 'JEWEL'

Thanks SE..

Reg,
Ishaan
Re: Remainders
by Jayesh Parmar - Tuesday, 1 September 2009, 08:05 AM
  Indeed a master piece, as always. smile
Re: Remainders
by Ronak kabani - Tuesday, 1 September 2009, 11:22 AM
 

SE Thanx a ton for ur efforts

Havent gone in detail

but definetely know it has to be amongst the best as it has always been

Dude plz keep the good work goin

Re: Remainders
by cat killer - Tuesday, 1 September 2009, 11:59 AM
  SE Bhai, you are gem of a person. Marvellous article indeed.
Re: Remainders
by sipra sahoo - Tuesday, 1 September 2009, 02:24 PM
  Ceratainly a brilliant article for fast calculation of remainders!
but i had a doubt; in the question 55^190 divided by 153, the last step is -35 mod 153. so shouldnt it be 118 mod 153 and not 120 mod 153?
morever ,i solved it by this way: 55^190.55^2 mod 153 = 1.55^2 mod 153 = 118 mod 153. thus the remainder should be 118. Is this correct?

In another question, 3^10 mod 341, i solved it this way:- 341=31x11.(there is an error where it is written that 341= 11x13).
 carm.fn(341) = lcm(cf(11),cf(31)) = lcm(10,30) = 30. thus 340 = 10 mod 30
3^10 mod 341 = 3^6.3^4 mod 341 = 47.81 mod 341 = 56 mod 341. Is this correct?
Re: Remainders
by Software Engineer - Tuesday, 1 September 2009, 02:53 PM
  Sipra,

     I could not interpret following line:-
55^190.55^2 mod 153 = 1.55^2 mod 153 = 118 mod 153. thus the remainder should be 118.

    hmmmm....... looks like a typo; I think the correct question is:- 3^340 = ? mod 143 or so.
Will check this later and tell you about this.

- SE
Re: Remainders
by sipra sahoo - Tuesday, 1 September 2009, 04:32 PM
  what i meant was 55^192 mod 153 is 1. we could write it as (55^190) x (55^2) mod 153 = R x (55^2) mod 153 (sorry for the typo error...) and instead of writing it as -35,i calculated it by using the positive remainder 118. the answer comes to be 118 in the end. is it correct?
Re: Remainders
by Software Engineer - Tuesday, 1 September 2009, 05:34 PM
  Sipra, Yes, it's correct.
Re: Remainders
by sipra sahoo - Tuesday, 1 September 2009, 06:10 PM
  Thank you! its really a very helpful article.. feel like I can solve any question on remainders now smile
Re: Remainders
by sridip sarkar - Tuesday, 1 September 2009, 06:57 PM
  what an article sir ji...

thanx a ton...!!

regards,

Sridip.
Re: Remainders
by userdce . - Tuesday, 1 September 2009, 09:55 PM
  just beautiful
Re: Remainders
by amit kumar - Wednesday, 2 September 2009, 12:22 AM
  nice Article.
thanks SE

Regards
Amit
Re: Remainders
by linkan sahu - Wednesday, 2 September 2009, 04:54 AM
 

this really helps.....

thanx a lot sirjeeeeeee.

keepupdating on these type of articles.....

Re: Remainders
by Sindhoor Grandhi - Wednesday, 2 September 2009, 10:13 AM
 

Great work.

Thanks SE .

Re: Remainders
by Ronak kabani - Wednesday, 2 September 2009, 03:51 PM
 

Dear SE

i Have a dbt

Q ) what is remainder 19^0 + 19^1 ...... 19^9001 is divided by 100

you have used modulus 100 and you are getting 20mod100

for

 Q ) what is remainder 19^0 + 19^1 ...... 19^91 is divided by 100

you have used modulus 10 and you are getting 20mod10

and then 0mod10

 

i didnt get then why in first case you used 100 and in second you used 10

getting two different answers you could have used modulus 10 in first case also na ?

plz explain

by the way ur article is simply superb

 

Ronak

Re: Remainders
by Software Engineer - Wednesday, 2 September 2009, 04:34 PM
  Ronak,

20 is the CMF value of 100. L(100)=20.
While 10 is the smallest exponent such that 19^10 = 1 mod 100; so 10 is MO of 19 (mod 100).

You can solve both puzzles by calculating L(100).
And you can also solve both puzzles by calculating MO of 19 (mod 100).

Choose the comparatively easier method.

- SE
Re: Remainders
by sipra sahoo - Wednesday, 2 September 2009, 04:58 PM
  in that case, if we keep on solving like the first method (as in question: 19^1 +19^2...19^9001 mod 100)the solution for 19^1+19^2.....19^91 mod 100 should also be 20 mod 100 i.e 20...  but your answer says 20 mod 10 = 0. why did you use 10 in place of 100?
Re: Remainders
by Software Engineer - Wednesday, 2 September 2009, 05:07 PM
  Ronak, Sipra,

That's another typing mistake. : (

Correct one:-
20 mod 100
Hence, answer is 20.

- SE
Re: Remainders
by Mahadevan V - Wednesday, 2 September 2009, 06:19 PM
  FaNtAbUlOuS... smile
Re: Remainders
by shashank prabhu - Thursday, 3 September 2009, 02:24 AM
  777^777 are the last 3 digits 973??
Re: Remainders
by the killer - Thursday, 3 September 2009, 04:40 PM
  Great artice SE sir..

this is going to be very helpful for everyone.

Regards,
The Killer
Re: Remainders
by ronak patel - Thursday, 3 September 2009, 07:13 PM
  very nice article for beginners like me.........
HOW 55^190=-35mod153 came to 55^190=120mod153?????
can't it be 55^190=118mod153?
please help me in this..  
Re: Remainders
by rajat sharma - Thursday, 3 September 2009, 09:10 PM
  hello i cannot get the first three calculations.as to what is modulo. n how modulo order of 13 is 2.plz help me out
Re: Remainders
by Bonhomie Fella - Friday, 4 September 2009, 01:04 AM
  this is the longest article in the history of TG, but one of the best. SE pls answer this question, are you also preparing for CAT 2009???? TG sir its been months we have not seen an article from you sir. You are writing for CAT CBT, we also desreve one sir, PLSSSSSSSSSSSS sir!!
Re: Remainders
by abhilash abhi - Friday, 4 September 2009, 01:33 AM
  mind blowing article...thnx very much bhai
expecting few more b4 the D-Day...
nice work...
Re: Remainders
by santhana lakshmanan - Friday, 4 September 2009, 02:38 AM
  When you write, " the remainder when bk is divided by n, is same as the unit digit of bk in base kyou actually mean bk in base n, dont you SE? Is this a typo ?
Re: Remainders
by Software Engineer - Friday, 4 September 2009, 11:05 AM
  Typing/Calculation mistakes:-
1. Hence, 55190 = -35 mod 153  or  55190 = 120 mod 153
   Hence, 55190 = -35 mod 153  or  55190 = 118 mod 153
2. Find the remainder when 3340 is divided by 341.
    Find the remainder when 3340 is divided by 143.
3. “Find the remainder when bK is divided by n.” equals “Find the units digit of bK in base b.” Why?
    “Find the remainder when bK is divided by n.” equals “Find the units digit of bK in base n.” Why?
4. = 20 mod 10 = 0 mod 10
   
20 mod 100  Hence, answer is 20.
Guys, any more?

Bonhomie, yes I am appearing to 2009. smile

- SE
Re: Remainders
by Mayank Chandna - Friday, 4 September 2009, 05:17 PM
  Thank you very very much SE..You have made our path to IIMs much easier..smile
Re: Remainders
by Hungry Gadha! - Friday, 4 September 2009, 06:14 PM
 

Hey SE,

Good worksmile

Also look at one Q'n...i.e. 22^1352  mod 52 is 16  not 14...check it out!

-HG

Re: Remainders
by Kunal Parekh - Friday, 4 September 2009, 08:07 PM
 

Dear SE,

Thank you very much for ths article...........

I have one doubt....in the last exampls of last 3 digits of 7^347.....i m nt able to get hw u took Lemda(100).......pls help me out

Kunal

Re: Remainders
by manoj kumar - Friday, 4 September 2009, 11:50 PM
  Dear SE,
Thanks a lot for this article... it has been a great help for all of us.. now i am sure i will be able to crack remainder questions easily...
Re: Remainders
by Software Engineer - Saturday, 5 September 2009, 07:14 PM
  Kunal,

Find the last three digits of b^K means Find the remainder when b^K is divided by 1000.

- SE
Re: Remainders
by Bruce Wayne - Saturday, 5 September 2009, 10:45 PM
  Amazing article... Mind blowing... increases speed so much. Thanks a lot SE.

Please post some more similar stuff that you have, someting similar for Algebra topics or any other topic.

Thanks again
Re: Remainders
by Kunal Parekh - Sunday, 6 September 2009, 11:17 PM
 

SE,

Thnx for ur post

That i got it.........but how lemda(1000)= 100 bcas i m getting less than that......I am missing sth and i am nt able correct it.......pls help me out.

Kunal

Re: Remainders
by Software Engineer - Monday, 7 September 2009, 11:47 AM
  Kunal,

1000=8*125. HCF[8, 125]=1.
L(1000) = LCM[L(8), L(125)] = LCM[2, 100] = 100.

- SE
Re: Remainders
by Sapanpreet Narang - Monday, 7 September 2009, 03:17 PM
 

Hi all,

Have a doubt.. plz help out….

Suppose we have something like…. Find d remainder when (9^10) is divided by 100.

In this case λ(100) = 20. since 9^10 = [3^2]^10 so k’ = λ(100)/2 = 20/2 = 10

Now in (9^10), 10 comes out equal to k’ (i.e 10) .. so how do we proceed ahead

Re: Remainders
by Kunal Parekh - Monday, 7 September 2009, 08:30 PM
 

SE,

I got it..............Thank you veru much again for your prompt reply.

Re: Remainders
by subhadip mahalanabish - Saturday, 12 September 2009, 03:26 PM
  hi Sapanpreet,

                            Lambda(100)=20, now 9^10 = 3^20, for  calculating remainder you have to divide  20 by lambda(100)  not lambda(100)/2.
So 20/lambda(100) = 20/20 = 0 . So kere K' = 0. So to calculate the remainder you have to calculate 3^0 mod 100 = 1 mod 100. So our answer will be 1.
Hope this helps you. If you still have doubts, my advice is just read the segment for calculating remainders using Carmichael's function. You will surely understand yourself. 

                                                                        regards,
                                                                                 Subhadip.
Re: Remainders
by subhadip mahalanabish - Saturday, 12 September 2009, 03:38 PM
  Dear SE,
                 Thanks a lot for this huge article. It is extremely  helpful for us since we are finding all the concepts for remainder problems in one place. Also the huge number of examples that you have given makes understanding even more easier. Great work.Cheers.

                                                 regards,
                                                         Subhadip.
Re: Remainders
by subhadip mahalanabish - Saturday, 12 September 2009, 10:05 PM
 

Dear SE,

                         In the problem  of finding  the remainder  of 2 ^ 1990 by 1990(posted by Rajarsi guha)  we are applying  Carmichael #1   thereby  we  should  write  1990 = 10 mod  396. But  in the article it is  given as  1990 = 10 mod 995 by mistake.  

                                                                                                                       Regards,

                                                                                                                                   Subhadip.     

Re: Remainders
by subhadip mahalanabish - Monday, 14 September 2009, 12:32 AM
  hi all,
          I have solved the problem of "consider the set S = {17^0,17^1,17^2.....17^2009} ..."
I am posting my solutions here, please post back your replies if you arrive at any different solution(s) or if you  have followed any different method(s).

Here are the solutions, please refer to the index number for finding the corresponding question:

1)lambda(26) = 12, hence modulo order of 17 mod 26 will be one among 1,2,3,4,6,12.By trial its
calculated to be 6. hence 17^6, 17^12, 17^18....mod 26= 1 mod 26, so number of elements in the set T
will be equal to number of terms of the a.p. series(6,12,....2004)(since 2009 is not divisible
by 6 so we have to  find a number just smaller than 2009 which is divisible by 6) the ans is 334.

2)modulo order of 17 mod 26 is 6. So the remainders when powers of 17
are divided by 26 will repeat themselves after multiples of powers of 6.
So we will get remainder 9 by dividing one among 17^1 ,or 17^2 or...17^5
by 26. By trial its calculated to be 17^4. Hence 17^4, 17^10...upto 17^2008(we have to stop at 2008 because we have to stop at a number which is less than 2009 and 4 more than a multiple of 6 just less than 2009 which is 2004.) will all have remainder 9 when divided by 26. Hence number of terms in the set T using same
logic of the previous problem will come out to  be 335.

3)Since modulo order of 17 mod 26 is 6 hence only 6 different remainders
are possible when powers of 17 are divided by 26. Hence there are 6 possible solutions for T.

4) Le 17^x and 17^y be two members of the given set, according to condition
17^x*17^y mod 26 = 1 mod 26. Hence x+y has to be a multiple of 6.
Lets consider 17^1 and 17^5 , their product 17^6 will give rem 1 on being divided by 26.
Now lets include 17^z also in the set T. By condition we must have 1+z= multiple of 6,
and 5+z= multiple of 6, which by observation is appearing to be impossible.
Hence we can't add any more elements in T.Hence there are only 2 members possible in T.
Ans 2.

5)Only 6 possible rem are possible when powers of 17 are divided 26 since modulo order
is 6. 17^1, 17^2, 17^3, 17^4,17^5, 17^6 gives remainders 17,3,25,9,23 and 1 respectively
on being divided bt 26. Now 17 + 3 = 20. Hence when 17^1 + 17^2 will be divided by 26 we will get remainder
of 20 and it will be repeated by continuosly adding 6 to 1 and 2 and dividing the sum of the respective
powers of 17 in each iteration.Ex: (17^7 + 17^8) mod 26= 20 mod 26.
Hence we will have the terams 17^1, 17^7, 17^13 upto 17^2005(we have to end in a number which is just less than 2009 and 1 greater than 2004,
because numbers in this sequence are all 1 greater than a multiple of 6.) and the terms
17^2,17^8....upto 17^2006(we have to end in a number which is just less than 2009 and 2 greater than 2004,
because numbers in this sequence are all
2 greater than a multiple of 6) absent in the given set T. The number of terms in each
sequence is 335 hence total is 670, so 2009-670 = 1339 terms will be there  in the set T.
ans 1339.

6)lambda(26) = 12, hence modulo order of 17 mod 26 will be one among 1,2,3,4,6,12.By trial its
calculated to be 6. hence 17^6, 17^12, 17^18....mod 26= 1 mod 26

and by MO#4 we must have 17^3,17^9....17^2007(we have to end in a number which is 3 more than 2004
which is the last multiple of 6 before 2009.) mod 26 = -1 mod 26.

lambda(14) = 6.hence modulo order will be one of 1,2,3,6 by trial found modulo
order = 6 hence 17^3 mod 14= -1 mod 14.Hence the series for 14 will be similar to
that for 26. Hence number of members in (S U T) will be equal to the number of terms
present on the a.p 3,6,.......2007. which comes out to be 669.So ans 669.

regards,
        Subhadip.
Re: Remainders
by subhadip mahalanabish - Wednesday, 16 September 2009, 12:19 AM
  Dear SE,
              In the problem of 2^2004 mod 2004,the final equation comes of the form R=4x=501y + 88, if we make it 4x - 88 = 501y. Now LHS must be a multiple of 501, so  x=275, then R = 275*4 = 1100. But  if we calculate like 4x = 501y+88(as you have done) =500y + y + 88 and cinsider y=0, then R = 88(here also if we put y=2 the R=1100.)So we are getting two remainders, 88 and 1100. Can you please explain the logic why 88 should be chosen in place  of 1100?If we do the mod div in calculator then also we will get 88. But then by what logic we can neglect 1100 and select 88??

                                          regards,
                                               Subhadip.
Re: Remainders
by ramya rao - Wednesday, 16 September 2009, 12:20 AM
 

hi can anyone pl solve this one

p,q and r are real numbers such that 2<p<4, 5<q<10 and 12<r<20. What is the smallest integer value that (pq + r) /  p can take? Ans options : a) 8 b) 11 c) 12 d) 9    and what is the largest integer value that (pq - r) / p can take? Ans options : a)  6 b) 7 c) 8 d) 9.

Re: Remainders
by Software Engineer - Wednesday, 16 September 2009, 12:29 PM
  Subhadip,

In the problem of 2^2004 mod 2004,the final equation comes of the form R=4x=501y + 88,
if we make it 4x - 88 = 501y.
Now LHS must be a multiple of 501, so  x=275,

   4x - 88
= 4*275 - 88
= 1100 - 88
= 1012 (this is not of the form 501y)

I think x=523.
R= 4*523 mod 2004
  = 2092 mod 2004
  = 88 mod 2004

- SE
Re: Remainders
by abhishek gupta - Wednesday, 16 September 2009, 11:13 PM
  great stuff  man!!    thanks

Re: Remainders
by sergey larry - Thursday, 17 September 2009, 01:30 AM
  solve dis: Find remainder when (100^3+101^3+102^3............................+198^3) is divided by 9.
Re: Remainders
by ROHIT K - Thursday, 17 September 2009, 11:00 AM
  Hi Sergey,

Q. Find remainder when (100^3+101^3+102^3............................+198^3) is divided by 9.

A. Remainder is 0.

100+101+..+198=14751 which is completely divisible by the dividend as the powers of the dividend are odd.

Also, 14751 is divisible by 9 (digital sum), Hence the remainder when (100^3+101^3+102^3............................+198^3) is divided by 9 is 0.

Please check if the answer is correct.

Hope this helps..smile

Rohit
Re: Remainders
by sergey larry - Thursday, 17 September 2009, 07:04 PM
  Rohit, can u plz explain this step:"100+101+..+198=14751 which is completely divisible by the dividend as the powers of the dividend are odd.Since the powers are odd,can we aply dis fr all odd powers.Consider dis:2^5+3^5+4^5=1299 dis should be divisble by 9 as (2+3+4=9)but it is not.Kindly explain ur solution as i may nt be understanding ur solution.Although the solution u gave,gives the right answer.

I gt one solution which says:sum of cubes of 3 cosecutive terms is always divisible by 9.hence the above terms make 33 such pairs and so gives the remainder zero.
Can anybody explain sum of cube of 3 consecutive terms funda.

Re: Remainders
by sergey larry - Friday, 18 September 2009, 12:48 AM
  SE cn u help
Re: Remainders
by Pyara gadha - Saturday, 19 September 2009, 01:08 AM
  Sum of three consecutive no.s=
(a-1)^3 + a^3 + (a+1)^3 = a^3 - 3a^2 + 3a -1 + 3a^3 + a^3 + 3a^2 + 3a + 1
                                 = 3a^3 + 6a
                                 = 3a(a^2+2)

Now if a is a multiple of 3 the this whole becomes a multiple pf 3*3 that's 9
If a= 3n+1
then 3(3n+1)(9n^2 + 6n + 1 + 2) = 3(3n+1)(9n^2+6n+3) =9(3n+1)(3n^2+2n+1)
which is again a multiple of 9
If a= 3n+2
then 3(3n+2)(9n^2 + 12n + 4 + 2) = 3(3n+2)(9n^2+12n+6)= 9(3n+2)(3n^2+4n+2)
again a multiple of 9

so 3a(a^2+2) is always a multiple of 9
or sum of three consecutive no.s is always a multiple of 9
Re: Remainders
by ROHIT K - Tuesday, 22 September 2009, 09:12 PM
  Hi sergey..

Sorry for the late reply..was busy lately and also did not check this thread..that's a very good point u raised(may b i have goofed up in the concept )..but if it is checked with other numbers it becomes true..i will try to find out the exact reason/concept and let u know about it. (TG if u r reading this post..kindly reply..)

Another method: (Hope there is a better method than this too..)

(100^3 + 101^3 +...+ 198^3) % 9

= ((198*199/2)^2 - (99*100/2)^2) % 9 (using summation of cube series formula)

= ((19701^2)-(4950^2)) % 9

= (24651*14751) % 9 ............(a^2-b^2=(a+b)(a-b))

= 0.......... (Digital sum %9)

Hope this helps..smile

Rohit



Re: Remainders
by sagar k - Wednesday, 7 October 2009, 07:53 AM
  least val 11 and max val 7
Re: Remainders
by Surendran s - Wednesday, 7 October 2009, 02:58 PM
 

Hi,

some of the image files are missing. can u plz rectify it

Re: Remainders
by praveen kumar - Monday, 12 October 2009, 04:32 PM
  hii sipra i'm new user of tg.actually its my first time to send any query to
any one.so if i hav any mistake then plz forget him.can u help me
actually my question on remainder.plz clarify method for solving to this question
plz...ya i knw its so-so question....but plz tell me its solution...

1.what is the remainder when 91+92+93+.........+999 is divided by 6?

                                            83
2.what is remainder when 6373   is divided by 13....?

reply soon plz
Re: Remainders
by praveen kumar - Wednesday, 14 October 2009, 05:54 PM
  hey tg group what happen guys
if any body know about answers of these question then plz
guy solve it and sent solution for my all query.plz guys
sad
Re: Remainders
by ROHIT K - Thursday, 22 October 2009, 07:31 PM
  Hi Praveen,

Is the answer

1. 3
2. 11

Kindly confirm, if correct i will post the solution.

Hope this helps..smile

Rohit
Re: Remainders
by smruty panigrahi - Friday, 23 October 2009, 10:51 AM
  Hii,

Yes rohit u r correct. Answers are 3 & 11.

OK help me out. In the above article in some of the solutions after
finding out lambda( i dont know where is t8 symbol in compu and i found it just now !! ) he has divided it with 2.

Check out the solution of 2^1990/1990 or the solution of 39^22/7

In both of them he has divided lambda by 2. Why ??

Thanx smile
Re: Remainders
by ROHIT K - Saturday, 24 October 2009, 09:53 AM
  Hi smruty,

That is how this method works.

Consider 3922 divided by 7

This is same as finding remainder when 422 is divided by 7.

Now 4 is 2(a perfect square) and L(7) = 6 has a factor of 2.

Hence we can divide L(7) by 2.

Rule:
Find the remainder when bk is divided by N when N is relatively prime to b.

If b is a perfect square and 2 is a factor of L(N) then find the remainder K' when K is divided by L(N)/2

If b is a perfect cube and 3 is a factor of L(N) then find the remainder K' when K is divided by L(N)/3

and so on and so forth for higher powers.

For 21990 divided by 1990

2 and 1990 are not co-prime. So Carmichael's Theorem cannot be applied.

The method for tackling such problem is stated in the post itself by taking H.C.F and dividing N by that H.C.F. and solving further.

Once you have divided 1990 (N in this case) by the H.C.F.(2,1990),there are no common factors between 2 and 995 (they are now co-prime), hence we can apply Carmichael's Theorem.

There is a typographical error in that problem
1990 is not 10 mod 995 but
1990 = 10 mod 396

Hope you have understood the correct version.

If you have doubt in that reply back to this post.

Hope this helps. smile

Rohit

p.s L(N) is lambda(N)
Re: Remainders
by Anoop Iyer - Monday, 26 October 2009, 01:12 PM
  Very good article exhaustive and very informative. Clear all concepts though felt bit complicated at first but very useful. Thanks a lot for putting this articles.
Re: Remainders
by Pallav Jain - Monday, 26 October 2009, 01:21 PM
  Hi Guys,

 Sorry fosting post this question in this Forum. Can u solve this question?

What is the product of all factors of the number N = 64 x 102, which are divisible by 5?

  12210 × 3102 × 5140
  22210 × 3140 × 5105
  32140 × 3210 × 5102
  42140 × 3102 × 5210
  52102 × 3210 × 5140

Regards

Pallav
Re: Remainders
by raja k - Monday, 26 October 2009, 01:49 PM
 

Hi SE sir u had done a great job for beginers like me......

sir i had a boubt in t5he following question.

find the remainder when 333435  is divided by 7..

remainder when 505635  is divisible by 11...

thnx in advance sir.

Re: Remainders
by amar goswami - Monday, 16 November 2009, 02:02 AM
  Hi SE,
   Article is indeed great and will be very helpful in everyone's prepn. Thanks for posting it.

Hi Praveen,

    There are lots of questions, similar to urs, already solved above in the article. Just go thru it and i m sure u will get it.

Rgds
Amar
Re: Remainders
by deepika gandhi - Tuesday, 17 November 2009, 01:39 PM
 


HI SE SIR..CAN U PLS GIV D SOLUTIONS FOR THE FOLLOWING Q POSTED BY RAJA...sad


find the remainder when 333435  is divided by 7..

remainder when 505635  is divisible by 11...

Re: Remainders
by amar goswami - Tuesday, 17 November 2009, 05:46 PM
  Hi Deepika,

    Please find the solution below:
33^34^35 / 7
33 and 7 are co prime hence lambeda= L(7)= 6
Now find the remainder of 34^35/6 using Carmichael # 1 theorem.
p=HCF [34,6] = 2,   q= 6/p =3
Hence remainder of 34^35/6 = remainder of 34^35/3 (apply Carmichael theorem)
L(3) = 2 , 35/2 = 1 and it would give us 34^35/3 = 34/3 =1
and our expression becomes
33^34^35/7 = 33/7 = 5 remainder.

Second question is also the same, try solving it or let me know if you need help.

Thanks
Amar
Re: Remainders
by deepika gandhi - Wednesday, 18 November 2009, 02:12 PM
  hi amar....
i have a doubt in basics itself....
how do v get 13^2=1 mod 24????sad

i hav tried d 2nd sum as per u said....
but got stuck at d end....

50^56^35/11
50 and 11 are co prime hence lambeda= L(11)= 10
Now the remainder of 56^35/10 using Carmichael # 1 theorem.
p=HCF [56,10] = 2,   q=10/p =5
so d remainder of 56^35/10 = remainder of 56^35/5
L(5) = 4 , 35/4= 3 and it would give us 56^35/5 = 56/5 =1?????
and then
50^56^35/11 = 50/11= 6 remainder?????


reply fastsad
Re: Remainders
by amar goswami - Wednesday, 18 November 2009, 02:16 PM
  Hi Deepika,

1. 13^2= 169 when divided by 24 remainder is 1.
2.  Which two questions you want me to explain??
3.  Where are u getting stuck, aa to gya answer 6 smile

Rgds
Amar
Re: Remainders
by deepika gandhi - Wednesday, 18 November 2009, 03:16 PM
  hi amar...thnxsmile
i thought that 6 is not d rite answer....
can u xplain me how d v get
5^10 = 1 mod 66
5^9*5=1 mod 66???????
few more quessadd doubts n ques r from dis article itself)
1) 5^48 = 1 mod 153
   5^46 * (-35) = 1 mod 153????

2) 39^22 divided by 7???

3) 37^47^57 divided by 16????


dipika
Re: Remainders
by amar goswami - Wednesday, 18 November 2009, 03:34 PM
  Hello Dipika


1. 5^10

66= 11*3*2 hence L(66)= LCM [ L(11), L(3), L(2) ] =LCM [ 10, 2, 1 ]

L(66) = 10 since b^L(n) gives 1 remainder hence 5^10 will 1 remainder.

2. I think u mean (5^9)*5

(5^9)*5 = 5^9 * 5^1 = 5^(9+1) = 5^10 since L(66) =10 hence 5^10 will give 1 remainder.

3. 5^48 = 1 mod 153

L(153) = LCM[L(17), L(9)] = LCM[16,6] = 48
hence 5^48 =1

4. 39^22 /7
L(7) = 6,   22/6 = 4 remainder
39^4/7 = (35+4)^4 /7 = 4^4 /7 = 16*16/7 = 4 remainder


Don worry how others are doing it, make sure u r following the correct approach and getting the right answer.

Rgds
Amar
Re: Remainders
by deepika gandhi - Wednesday, 18 November 2009, 03:56 PM
  hi amar...thanx....


u r really helping me.....
deepika
Re: Remainders
by amar goswami - Wednesday, 18 November 2009, 04:14 PM
  not a problem.. its the least we all can do for TG by helping each n everyone who comes at TG site and asks for help.. smile
Re: Remainders
by deepika gandhi - Wednesday, 18 November 2009, 06:15 PM
  hi amar...wats d appraoch 4 dis q...

What is the product of all factors of the number N = 64 x 102, which are divisible by 5?

  12210 × 3102 × 5140
  22210 × 3140 × 5105
  32140 × 3210 × 5102
  42140 × 3102 × 5210
  52102 × 3210 × 5140

deepika
Re: Remainders
by Pallav Jain - Wednesday, 18 November 2009, 07:46 PM
  1st of all I am really sry Guys for posting TSD in this coloum reason being I hv posted twice this prob but no 1 is checking TSD coloum. sad

A starts from home for his office. He travels downhill, then on flat ground and then uphill to reach his office. It takes him 3 hrs to reach the office. On the way back home A takes 3 hrs 10 min to reach home along the same route. The speeds downhill is 60 km/hr, on flat ground is 48 km/hr and uphill is 40 km/hr.

What is the distance between A’s home and his office?
144 km
148 km
154 km
160 km
Data Insufficient

Cheers !!!!!!

Pallav

Re: Remainders
by amar goswami - Wednesday, 18 November 2009, 08:30 PM
  N = 64 x 102 = 26 *34 * 52

Method 1 :
a number divisible by 5 will have 5 in it hence we need to check how many such numbers are possible.
2^0 * 3^0 * 5^1
2^0 * 3^0 * 5^2
2^0 * 3^1 * 5^1
2^0 * 3^1 * 5^2
2^0 * 3^2 * 5^1
2^0 * 3^2 * 5^2
.
.
2^0 * 3^4 * 5^1
2^0 * 3^4 * 5^2
we recieved 10 such numbers for 2^0 now we need to do the same for 2^1 then 2^2..upto 2^6 which will give us total 70 such numbers.
now to reach the answer we need to see what number is coming how many times in the product?
if we multiply all the numbers having 2^0 power, scenario for 3 and 5 will be:
3^(0+0+1+1+2+2+...+4+4)  = 3^20
similarly 5^(1+2+1+2...1+2) = 5^15
this is for first 10 numbers and when we take all the numbers (70) together, final power of 3 will be (3^20)7 i.e.  3^140
and  5^(15)7 = 5^105 which gives us choice 2 as answer.


Method 2:
N = 64 x 102 = 26 *34 * 52
No. of divisors of N are 7*5*3 =105
Now out of these 105 numbers, 35 contain 5^0 power(these needs to be excluded as these are not divisible by 5) another 35 contain 5^1 and last 35 contain 5^2 power.
if we multiply these 70 divisors and consider the scenario only for 5 :
 (5^1 * 5^1 * .. 35 times)*(5^2 * 5^2 * .. 35 times)
from this product Final power of 5 will be 105 hence choice 2 as answer.

Regards
Amar








Re: Remainders
by deepika gandhi - Wednesday, 18 November 2009, 08:58 PM
  hey amar....
thnx a lot man







deepika
Re: Remainders
by amar goswami - Wednesday, 18 November 2009, 09:23 PM
  Hi Pallav,

    I have replied to ur question in TSD section. Sorry for late reply man, i started my revision with number system topic and was checking posts related to it only. Gotta finish all within this week.  smile

Rgds
Amar
Re: Remainders
by deepika gandhi - Wednesday, 18 November 2009, 10:27 PM
  hi amar...
1 more doubtsad



12^600 divided by 100???????


12^20 mod 100
4^20 * 3^20 mod 100
76 * 01 mod 100????
 
i dint get dis step...can u help me out
Re: Remainders
by amar goswami - Wednesday, 18 November 2009, 11:21 PM
  Hi Deepika,

  12 and 100 are not co prime you need to keep it in mind if you apply any remainder theorem here. However problem can be easily solved without getting into all that.

12^600  last two digits of the expression will be remainder when it is divided by 100.

12^600 =  4^600 * 3^600  =  2^1200 * 3^600  = (2^10)120 * (3^4)150
which is equal to
24^120 * 81^150  = 76 *01 = 76 answer
because 24^even power = 76
and for a no. ending with 1, 10th digit = 8*0 =0 and unit digit is always =1

 
Re: Remainders
by deepika gandhi - Thursday, 19 November 2009, 12:15 AM
  hey amar...
thnx yar...i got d sum now...

deepika
Re: Remainders
by Pallav Jain - Thursday, 19 November 2009, 02:49 AM
  Amar your steps can be reduced as
(10+2)^600
10^600 No remainder
(2^10)^60 same 1024^60
LAST  2 DIGITS ARE 76


Re: Remainders
by litty ignatius - Tuesday, 24 November 2009, 10:39 PM
 
what is the remainder when (17(9!) + 18!)  is divided by (9! * 8704 )????




Re: Remainders
by Abhijit Doke - Sunday, 29 November 2009, 04:17 PM
  what is the remainder when sum of squares factorials of first 20 natural numbers is divided by 1152 ???
Re: Remainders
by sriram Kothandaraman - Wednesday, 2 December 2009, 08:43 AM
  What is the remainder of 34! divided by 71 ... anybody please help...
Re: Remainders
by The One - Saturday, 16 January 2010, 07:01 PM
  Superb article....!!!!!!!!
Re: Remainders
by Software Engineer - Sunday, 17 January 2010, 12:05 AM
  The One(Op),

Was it *really* superb? ;)

Was wondering, what things did you like and what you didn't?

Would like your feedback/thoughts!

- SE
Re: Remainders
by prasanth warrier - Sunday, 17 January 2010, 10:10 AM
  sorry SE i dint understand anything from the beggining...frankly speaking i dint get how 13^2 is 1 mod24...i donno the concept of mod ...can u tell me page wer i can refer it

Re: Remainders
by Software Engineer - Sunday, 17 January 2010, 11:25 AM
  Prasanth,

Conventions may vary from one person to another:
169 = 1 mod 24
169 mod 24 = 1
[169/24] = 1
169 = 24*7 + 1
but they all mean one thing:- The remainder when 169 divided by 24 is 1.

Mod = Modulo = Remainder produced by division operation.

- SE
Re: Remainders
by xlr pmir - Thursday, 13 May 2010, 03:26 PM
  hey greata article. im confident of remainders now
Re: Remainders
by sandhya belkar - Tuesday, 1 June 2010, 03:01 PM
  hey
i didn't understand nythng
it ws all bouncer
Re: Remainders
by Arun Pratap Singh - Sunday, 11 July 2010, 01:05 AM
  what is the remainder when (17(9!) + 18!)  is divided by (9! * 8704 )????

Answer is 9!
Re: Remainders
by Abhirup DebRay - Sunday, 11 July 2010, 09:17 AM
  dude d ans is 17(9!) & not 9! smile
Re:Remainders
by imteyaz mohsin - Tuesday, 24 August 2010, 02:14 PM
  Awesome and mind blowing article...
It has been a privilege that we have such a teacher like u..
Re:Remainders
by chetan chandrashekar - Wednesday, 25 August 2010, 06:54 PM
  Hi,

I recently came across the que to find the remainder for
(15^400)/1309

Can anyone pls let me know how to solve it.
Re:Remainders
by Gaurav Verma - Thursday, 26 August 2010, 07:50 AM
  IS the remainder 135..
Re:Remainders
by chetan chandrashekar - Thursday, 26 August 2010, 12:20 PM
  Hi Gaurav,

Thanks for solving.
But i recently came across this in one of the TIME tests and dont know the answer and how to solve.
Can u pls elaborate on how u solved it
Re:Remainders
by TG Team - Thursday, 26 August 2010, 01:57 PM
 

Hi Chetan smile

1309 = 7*11*17

So find the remainder of 15400 with 7, 11 and 17 individually and then combine them using Chinese Remainder Theorem to get the final answer.

Re:Remainders
by chetan chandrashekar - Thursday, 26 August 2010, 06:11 PM
  Hi kamal,

I know chinese theorem but will it not be two much of a time to solve it!!!!
Re:Remainders
by TG Team - Thursday, 26 August 2010, 06:48 PM
 

15400 = 1 mod7 = 1 mod17 = 1 mod119 = 1 mod 11 = 1 mod1309. smile

Was that lengthy? I didn't use paper-pen to figure it out. smile

Re: Remainders
by Deepak Kumar - Friday, 27 August 2010, 06:51 AM
  Using carmichael's theorem,
someone solve this pl..

3^4/6???
Re: Remainders
by Himanshu Goyal - Wednesday, 29 September 2010, 12:46 PM
  2^1500 / 13 =????
Re: Remainders
by Abhirup DebRay - Wednesday, 29 September 2010, 12:49 PM
  1
Re: Remainders
by amit solanki - Saturday, 2 October 2010, 05:19 PM
  I'hv one question pertaining to remainder only, kindly throw some light.

When 4^101 + 6^101 is divided by 25, the
remainder is, options are {20,10,5,0}.
Re: Remainders
by ravi kumar - Sunday, 3 October 2010, 01:06 AM
  @amit
4^20/25 =1 (by Euler's theorem)so
((4^20)^5.4)/25=4
similarly ,for 6^101/25=6(remainder)
so the ans is 10
Re: Remainders
by abhishek srivastava - Sunday, 3 October 2010, 01:18 PM
 

I have a doubt ...in

The number 84^86 when converted to base 210 ends in digit______???

+++++++++++++++++++++++++++++++++++++++++++++++++++

in one of ur discussion forum (http://totalgadha.com/mod/forum/discuss.php?d=5224), ther is a problem


"The number 2006! is written in base 22.How many zeros are there at the end???"

in solution u have suggested to find out the remainder .

the same concept u r using here(The number 84^86 when converted to base 210 ends in digit______????) to find out the unti digit ...Can u pls tell me hw is it possible that the same remainder will give u total no of trailing zeros as well as the unit digit.

Help me....

Re:Remainders
by nikita dhanuka - Saturday, 9 October 2010, 10:37 AM
  hi

i have a doubt

find the remainder when
(123412341234....repeated 300 times) is divided by 909.

i have solved this question and got my answer as 237. please check whether my answer is correct or not.

thanks and regards
nikita
Re: Remainders
by late starter - Friday, 29 October 2010, 12:07 PM
  question -
we know that 2n! is divisible by (n! * n!)
can u generalize its remainder?
Re: Remainders
by jg hbhhbbh - Wednesday, 2 March 2011, 03:19 AM
 

hello sir.

  it's a faadu article .

 but one doubt

 i  am able to solve problems v v v easily but  plz give me full proof of carmicheal's theorem with an example. like 12^100 when divided by 67 gives what remainder. i know how to crack. jus solve 12^34 by 67 ;the same can be solved by binary system or any other method.but i didnet get in my mind that how we can say 12^34 or12^100 gives same remainder when divided by 67; or in other words i want to ask about detailed proof of carmicheal's theorem

Re: Remainders
by mansi goel - Thursday, 27 October 2011, 12:56 PM
  Sir,
Please help me with these ques:

find remainder when
(17)^36 + (19)^36 is divided by 11; 128^500 is divided by 153
Re: Remainders
by amit gupta - Thursday, 27 October 2011, 01:31 PM
  1. 17^36 + 19^36 mod 11
Soln: 11 is prime. Thus, Euler function of 11 = 10

hence, 17^10 mod 11 = 1... similary 17^36= [(17^10)^3] * 17^6... First part would give a remainder of 1.. thus sum reduces to 17^6 mod 11... 17^2 = 289 leaves a remainder of 3 with 11. Thus find remainder of 3^3 with 11...which will give 5

Similarly solve for 19^36... will give a remainder of 3...
Thus, finally add both to get the final answer as 8..

Please note that this is the basic approach to these kind of problems.

2. 128^500 mod 153
153= 17*9

Find individual remainders for 17 and 9 which would come out to be 16 and 4 respectively.

Now the reqd. remainder R = 17x + 16 = 9y + 4..

Solving we get, x=3 and y=7.. substitute and you get the answer as 67...

If someone has a better approach... please do mention.

Regards,
Amit
Re: Remainders
by Mohit Sharma - Monday, 2 April 2012, 05:43 PM
  Hi Sir,
As usual a great article again. Your level of work is really respectable. Sir if you can help me out with the following question,

Ques: What will be the remainder when 128^1000 is divided by 153?

Please help me out sir.
Re: Remainders
by arsh arora - Tuesday, 3 April 2012, 10:06 AM
 

hi mohit,

      92 will be the remainder ...use neg. rem here,u will get -25*82/153

then,simply multiply numerator terms and divide...will get -61/153 which is 92...

Re: Remainders
by Mohit Sharma - Tuesday, 3 April 2012, 03:44 PM
  hi arsh,
I too tried the same procedure but didnt get any of the options. can you explain ur method. And also the options given were,
1) 103
2) 145
3) 118
4) 52
Re: Remainders
by arsh arora - Tuesday, 3 April 2012, 05:38 PM
  hi mohit, i had checked it wid calci also 836(quotient) * 153=127908 which is 92 less than 128000...options are wrong man!!! i had used neg.remainder cncept..hope u know it!!
Re: Remainders
by TG Team - Wednesday, 4 April 2012, 12:30 PM
 

I guess, I've answered this question many times earlier also. Anyways, see it once more smile

153 = 9 × 17

So, we need to find the remainder obtained for the number 1281000 with the two divisors and then combine them using some method. Also there is no use of combining the two remainders obtained if options are available, as in this case. So here we just need to check that which option gives the same remainder with the divisors 9 and 17 as obtained by the number.

Now let's find the remainder of the number with 9 and 17.

1281000 = 21000 mod9 = (2³)333 × 2 mod9 = (-1)333 × 2 mod9 = -2 mod9 = 7 mod9.

So our answer should also be giving remainder 7 when divided by 9. Only 52 satisfies. So if answer is one of the options, then it should be 52.

1281000 = 91000 mod17 = (9²)500 mod17 = (-4)500 = 21000 mod17 = (24)250 mod17 = (-1)250 mod17 = 1 mod17.

That means number gives remainder 1 when divided by 17, so our answer should be like that also. And again 52 satisfies. Hence 52 is the answer. smile

Kamal Lohia 

Re: Remainders
by arsh arora - Wednesday, 4 April 2012, 12:52 PM
  thanks sir for correcting me!!!!
Re: Remainders
by arsh arora - Wednesday, 4 April 2012, 01:01 PM
 

hello kamal sir,

              can u plz explain why am not getting the same answer by using neg.remainder concept????

Re: Remainders
by TG Team - Wednesday, 4 April 2012, 01:29 PM
 

Arsh smile

-25 is ok but what is this 82?

1281000 = (-25)1000 mod153.

And as HCF(128, 153) = 1 we can apply Euler's Theorem which says 128phi(153) = 1 mod153. Now phi(153) = 153 (1 - 1/17)(1 - 1/3) = 96.

So we have now  1281000 = (-25)1000 mod153 = (25)1000 mod153 = (2596)10 ×2540 mod153 = 2540 mod153 = (25²)20 mod153 = 1320 mod153 = (13²)10 mod153 = 1610 mod153 = (16²)5 mod153 = (-50)5 mod153 = (-50)(50²)² mod153 = (-50)(52)² mod153 = (-50)(-50) mod153 = 50² mod153 = 52 mod153. smile

Kamal Lohia

Re: Remainders
by arsh arora - Wednesday, 4 April 2012, 01:47 PM
 

hello sir,

              my mistake...from the starting ,am taking it as 128 * 1000 instead of 128^1000..smile

Re: Remainders
by arsh arora - Wednesday, 4 April 2012, 01:53 PM
 

hey mohit,

yaar 52 will be the answer as explained by kamal sir, i had mistakenly took question as 128 * 1000 instead of the original statement as  128 ^ 1000.

Re: Remainders
by Mohit Sharma - Wednesday, 4 April 2012, 07:02 PM
  hi kamal sir,
Thanks for the ans. It is the right one. But one more thing, I'm not able to get how you get this
128^1000 = 2^1000 mod9
I guess it should be
2^7000 mod9.
Please help me.
Re: Remainders
by arsh arora - Wednesday, 4 April 2012, 07:33 PM
 

hi mohit,

as 128/9= 2 thats why...i think u shud revise remainder theorem buddy!!

Re: Remainders
by Mohit Sharma - Wednesday, 4 April 2012, 07:37 PM
  Thanks arsh... i got confused with other theorem... but yeah i will revise it again...
Re: Remainders
by viewpt kr - Tuesday, 10 July 2012, 01:50 AM
  Guys hw to find last 2 non zero digits of any factorial???
take:

1) 154 !
2) 200 !
3) 89!

plz xplain ????

Re: Remainders
by TG Team - Tuesday, 10 July 2012, 05:13 AM
 

Hi viewpt krsmile

I have already written much about this thing in my Math Corner. The first and last both posts talk about "How to find last one/two non-zero digits in a factorial number" mathematically.

Hope it helps. smile

Kamal Lohia