wht is remainder when 128^1000 is divided by 153..?

• 128^1000/153 = 128^1000/17.9
  
  now when 128^1000 is divided by 17 rem
  
  2^7000/17 = 16^1750/17 = (17-1)^1750/17 so rem = 1
  
  it can be represented by 17a +1.............(1)
  
  when 128^1000 is divided by 9
  
  2(3*333 + 1)mod9 = -1*2mod9 = 7mod9 so rem = -1.2 = -2 = 7
  
  it can be represented by 9b + 7............(2)
  
  equating (1) and (2)
  
  17a+1=9b+7 => 9(b-a) = 8a - 6
  this is true for a = 3
  
  so remainder = 17*3 +1 = 52
• 12 years agoHelpfull: Yes(35) No(38)
• 128^1000 = (153-25)^1000 = (25^1000)mod153 = (625^500)mod153 = [(4*153+13)^500]mod153 = (13^500)mod153 = (169^250)mod153 = [(153+16)^250]mod153 = (16^250)mod153 = (256^125)mod153 = [(153+103)^125]mod153 = (103^125)mod153
  = [(2*3*17+1)^125]mod153
  
  At this point,observe that 153=17*(3^2);
  
  Now,therefore clearly (2*3*17+1)^125 = [(125C124)*{(2*3*17)^1}*(1^124)+1]mod153.
  
  Actually,the above line can be written since only except the last two
  
  terms,every term of the expansion of (2*3*17+1)^125 has [(2*3*17)^2],i.e,
  
  [153*68] as one of its factors.
  
  Now, [(125C124)*{(2*3*17)^1}*(1^124)+1]= 125*2*3*17 + 1;
  
  [125*2*3*17 + 1]/(153) = [125*2*3*17 + 1]/(3^2*17) = (125*2*3*17)/(3^2*17) +
  
  1/(3^2*17) = 250/3 + 1/(3^2*17) =83 + (1/3)+ 1/(3^2*17) = 83 + (52/153);
  
  which means [125*2*3*17 + 1] = 83*153 + 52;
  
  which again implies 128^1000 = [125*2*3*17 + 1]mod153 = {83*153 + 52}mod153 =
  
  52mod153 ;
  
  So, remainder is 52.
  
• 12 years agoHelpfull: Yes(19) No(11)
• 52 is the remainder.
  
  
  128^1000 / 153
  proceed this prob as previous 1 which u asked,
  128^1 = -25 mod(153) i.e. 128-153
  128^2= (-25)^2 = 625 mod 153 = 13
  128^4 = 13^2 = 169 mod153 = 16
  128^8 = 16^2 = 256 mod 153 = 103
  128^16 = 103^2 = 10609 mod 153 = 52
  128^32 = 52^2 = 2704 mod 153 = 103
  128^64 = 103^2 = 10609 mod 153 = 52
  128^128 = 52^2 = 2704 mod 153 = 103
  128^256 = 103^2 = 10609 mod 153 = 52
  128^512 = 52^2 = 2704 mod 153 = 103
  finally for 128^1000 we can re-write it as : 128^512 * 128^256 * 128^128 * 128^64*128^32 * 128^8
  which is equals to
  = > { 103 * 52 * 103 * 52 * 103 * 103 } mod 153
  => 103 ^2 Mod 153 * 52* 52 * 103 * 103
  = > 52 *52*52* 103 ^2 Mod 153
  => { 52 * 52*52* 52 } mod 153
  = > 52^2 mod 153 * 52^2
  = > 103 * 103 mod 153 ( i.e. similarly for 52^2 mod 153 = 103)
  = > 52 .
• 12 years agoHelpfull: Yes(10) No(12)
• @ ANKUR TRIVEDI :
  
  You are most welcome & thanks a lot to u too.I'm really feeling honored due to
  
  the fact that I've got at least some1 who,expending a considerable amount of
  
  his valuable time, have noticed and most importantly acknowledged the solution
  
  I've posted.
  
  I'm really feeling gratified due to your precious feedback.
  
  Thank u soo much 1ce again..:-):-)
• 12 years agoHelpfull: Yes(7) No(6)
• @ Sdeep Bhattacharya:
  yes you gives a very nice solution,but at the time of paper we have not enough time for doing this big solution,and also time consuming.
  is there are shortcut method for doing this type of questions?
• 12 years agoHelpfull: Yes(5) No(6)
• 153 = 32*17 = 9*17
  
  and 1281000 = 21000mod9 = 2(3*333 + 1)mod9 = -1*2mod9 = 7mod9.
  
  also 1281000 = (-8)1000mod17 = 23000mod17 = 24*750mod17 = 1mod17.
  
  Also 9*2 - 17*1 = 1
  
  Using Chinese Remainder Theorem
  
  128^1000 = (9*2*1 - 17*1*7)mod153 = -101mod153 = 52mod153
  This is simply application of Chinese Remainder Theorem.
  
  For two divisors D1 and D2 such that HCF(D1 , D2) = 1, first find integers x, y so that xD1 + yD2 = 1
  
  Next let N ≡ r1 mod D1
  
  and also N ≡ r2 mod D2
  
  Then according to Chinese Remainder Theorem (CRT):
  
  N ≡ (xD1r2 + yD2r1) mod D1D2. so answer wud be 52
  
• 11 years agoHelpfull: Yes(4) No(1)
• We have to find out Rem [128^1000/153]
  
  This looks a little difficult if you do not any theorems for finding out remainders. Let us take a simpler approach and break down the problem into smaller parts.
  
  These type of questions become really simple if you understand the concept of negative remainders. Always try and reduce the dividend to 1 or -1.
  
  153 = 9*17
  128^1000 = 2^7000
  
  Let us find out Rem[2^7000/9] and Rem[2^7000/17]
  We will combine them later.
  
  Rem[2^7000/9]
  = Rem [ 2^6999 x 2 / 9]
  = Rem [ 8^2333 x 2 / 9]
  = Rem [ (-1)^2333 x 2 / 9]
  = Rem [ (-1) x 2 / 9]
  = - 2 from 9
  = 7
  
  Rem[2^7000/17]
  = Rem [16^1750 / 17]
  = Rem [ (-1)^1750 / 17]
  = 1
  
  So, our answer is a number which leaves a remainder of 7 when divided by 9 and it should leave a remainder of 1 when divided by 17.
  
  Let us start considering all numbers that leave a remainder of 1 when divided by 17
  => 18 (leaves a remainder of 0 from 9. Invalid)
  => 35 (leaves a remainder of 8 from 9. Invalid)
  => 52 (leaves a remainder of 7 from 9. Valid. This is our answer)
  
  I have answered a bunch of very similar questions on remainders. You can get the complete list here: Remainder Theorem and related concepts for CAT Preparation by Ravi Handa on CAT Preparation
• 7 years agoHelpfull: Yes(3) No(0)
• first of all we will write 128^1000 =(128^2)^500.ie 16384^500.
  now in this type of case we divide power by 4 and check the remainder.when we will divide 500 by 4 then remainder will be zero.so .we will divide 16384 by 153.and take the remainder.so remainder will be 13.
• 12 years agoHelpfull: Yes(2) No(27)
• SDeep Bhattacharya ,thank you for detail.now i am agree with you.
• 12 years agoHelpfull: Yes(1) No(9)
• This is so awesome question....in this we have to divide 153 as a product of 2 coprime numbers i.e 17*9
  now we will calculate 2^1000/9 and 2^1000/17 leaves the reaminder 16 and 7 respectively
  let N= 2^1000
  so now N=17 a+16
  and N=9b+7
  so checking for values of 17a+b that willl give remainder of 7 when divided by 9
  so i.e 16 so general for of number is N=153*a+16
  
  
  
• 9 years agoHelpfull: Yes(1) No(1)
• 153=17*9
  divide 128^1000 by both individually
  
  128^1000/9=(2+126)^1000/9=2^1000/9
  remainder for this is 7
  
  128^1000/17
  Note:For any prime number , k^p-1/p leaves remainder 1,here 128^16/17 would leave remainder as 1.
  hence 128^1000=128^8/17=9^8/17 =13^4/17 =1
  
  9x+7=17y+1
  x=5 satisifes
  hence 52
• 7 years agoHelpfull: Yes(1) No(0)
• (8^4)/153=84
• 12 years agoHelpfull: Yes(0) No(11)
• cool answer guys,,,,
  but according to me the solutions is something like....
  (128)^(20*50)......ie remindr of (any no)^20 = 00 ie its circle gets completed
  thus 128 is the answer
  ;)
  
  
• 9 years agoHelpfull: Yes(0) No(3)
• I am using the concept of Euler Number to Solve this Question
  
  For those who dont know what euler no. is
  E(n) for a natural number n is defined as number of numbers co-prime to n
  
  It can be found out by following method
  
  1) Split the required number into its prime factors
  153 = 3^2 * 17
  
  2) multiply the no. with (1-reciprocal of the prime factor)
  
  E(n) = 153 * (1-1/3)(1-1/17) = 96
  
  now if A^n/P where A and P are co-prime then Rem[(A^E(P))/P] = 1
  
  here in this question as already found out above euler of 153 = 96
  
  so since 128 and 153 are co prime => R[128^96/153] = 1
  
  => equation reduces to [128^(10.96).128^40]/153
  
  =>128^40/153
  
  now 128 = 153-25
  
  so (-25)^40/153 => (25^40)/153
  
  => 625^20/153 => (612+13)^20/153 = 13^20/153 = 169^10/153 = (153+16)^10/153 = 16^10/153 = (256)^5/153 = (-50)^5/153 = (2500)^2.(-50)/153 = 52^2.(-50)/153 = 103.(-50)/153 = -50.-50/153 = 2500/153 = 52
  
  => this gives remainder = 52
• 8 years agoHelpfull: Yes(0) No(1)
• its ans will be 0
• 8 years agoHelpfull: Yes(0) No(1)