Find remainder of 128^1000 divided by 153??

• 128^500, just try to divide 128 by 153, the remainder is 128 a very big no, u have to make this number smaller and smaller.
  now think of 128^2 = 16384, which on division by 153 gives, 13 as the remainder.
  so we can write
  128^500 = ((128)^2)^250
  = (13)^250 (remainder on division by 153)
  = (169)^125
  = (16)^125 (remainder on division by 153)
  = ((16)^5)^3
  = (52)^3 (remainder on dividing 16^5 = 65536 by 153 is 52)
  = 140608
  = 1 (Dividing 140608 by 153 leaves the remainder 1)
• 11 years agoHelpfull: Yes(6) No(1)
• we know if n=even, ((x^n)-(a^n)) is completely divisible by x+a; so...as n=1000...(128^1000-25^1000) is completely divisible by 153...so finally the remainder will be 25...
• 11 years agoHelpfull: Yes(2) No(2)
• Well not as simple as it looks.
  Charmichael number for 153 is 48
  1000 mod 48= 40
  128^40 or (-25)^40 or 625^20
  13^20 mod 153
  16^10 mod 153
  keep solving little more and you'll get 52(ans)
• 11 years agoHelpfull: Yes(1) No(5)
• Easier alternative:
  128=2^7
  So 128^40=2^280
  280 mod 48 =40
  so equation is reduced to:
  2^40 mod 153
  (1024)^4 mod 153
  106^4 mod 153
  67^2 mod 153
  =52
• 11 years agoHelpfull: Yes(1) No(4)
• 52 is the correct answer.
• 7 years agoHelpfull: Yes(0) No(0)