remainder when 128^1000 is divided by 153

• Ans is:52
  128^1000/153
  (128^2)^500/153
  (16384) by 153 reminder=13
  (13^2)^250/153
  =(169)/153 reminder=16
  Now 16^250/153
  (16^6)^41*(16^4)/153
  =(16^6)=16777216/153 Reminder 1
  =(16^4)=65536/153 Reminder 52
  So 52*1=52
  Ans is 52
• 10 years agoHelpfull: Yes(7) No(1)
• 128^1000/153
  =(128*128)^500/153
  when we divide (128*128) by 153 reminder=13
  so,(13^500)/153
  =(169)^250/153
  here 169/153 reminder=16
  so,16^250/153
  ={(16^6)^41+16^4}/153
  =(16^6)^41/153+16^4/153
  here (16^6)/153..reminder=1 and 16^4/153 reminder=52
  so(1^41)+53=53 is the reminder...
• 10 years agoHelpfull: Yes(4) No(4)
• 128*128 divided by 153 remainder is zero.then 128^100 divided by 153 remainder is zero
  
• 10 years agoHelpfull: Yes(0) No(8)
• 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.
  
• 9 years agoHelpfull: Yes(0) No(0)
• 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)
• 9 years agoHelpfull: Yes(0) No(0)