Question

what is the remainder of 128^500 divided by 153

Answer 1

Heya user,
_____________________________________________________________

128 = 2^7;

=> We've to find 2^(3500) [mod 153]

_____________________________________________________________

Now,
Ф(153) = 96;
By Euler's theorem, 2^24 ≡ 1 (mod 153)

===> 2^24 ≡ 1 (mod 153)
===> 2 ^ (24 * 145) ≡ 1 (mod 153)
===> 2 ^ (3480) ≡ 1 (mod 153)

Also, 2^20 = 1048576 ≡ 67 (mod 153)

.'. 2^( 3480 + 20 ) ≡ 67 (mod 153)
or 2^3500 ≡ 67 (mod 153)
or 128^500 ≡ 67(mod 153)

Hence, remainder, when 128^500 is divided by 153 is 67....

_____________________________________________________________

Answer 2

the reminder is 67......