128^1000 divided by 153 ? remainder

• 128^1000 mod 153
  (2^7)^1000 mod 153
  2^7000 mod 153
  We can use Euler's theorem since 2 nd 153 are co-primes...
  Euler value of 153 is E(153)= 96
  So 2^E(153)=1
  (2^96)^72 * 2^88 mod 153
  1 * 2^88 mod 153
  
  153 => 9 * 17 [a=9, b=17]
  Rem[2^88/9] = r1
  Rem[2^88/17] = r2
  
  E(9) = 6
  (2^6)^14 * 2^4 mod 9
  1 * 16 mod 9
  7 mod 9
  r1 = 7
  
  E(17) = 16
  (2^16)^5 * 2^8 mod 17
  1 * 256 mod 17
  1 * 1 mod 7
  r2 = 1
  
  Remainder = ax+r1 = by+r2
  Remainder = 9x+7 = 17y+1
  Remainder = 52 [x=5, y=3]
  
  Ans : 52
  
  
• 10 years agoHelpfull: Yes(8) No(0)
• i thinnk 50
  128=2^7
  128^1000=2^7000/153
  153=3*51
  =2^7000/3*51
  =(-1)^7000/51
  =1/51
  =51-1=50
  
• 10 years agoHelpfull: Yes(0) No(2)