I have tried for almost more than an hour to find the remainder of the following
$\frac{128^{1000}}{153}$
I applied remainder theorem to get the answer but could not succeed. Any suggestion or help is appreciated.
Thanks.
I have tried for almost more than an hour to find the remainder of the following
$\frac{128^{1000}}{153}$
I applied remainder theorem to get the answer but could not succeed. Any suggestion or help is appreciated.
Thanks.
The main observation is that the powers $a^n$ of an integer $a$ must repeat modulo $m$ because there are only $m$ possible remainders. Once it does repeat, it repeats periodically. The period may be less than $m$.
Since $153 = 9\times 17$, consider the powers of 2 modulo 9 and 17.
Modulo 9, the powers of 2 repeat with period 6.
Modulo 17, the powers of 2 repeat with period 8.
Therefore, modulo 153 the powers of 2 repeat with period $\hbox{lcm}(6,8)=24$.
Finally, note that $128^{1000}= 2^{7000}$ and $7000 \equiv 16 \bmod 24$.
Hence, $128^{1000} \equiv 2^{16} \equiv 52 \bmod 153$.
You can raise a number $x$ to the power 1000 by the following steps: square it, multiply by $x$, square, multiply by $x$, square, multiply by $x$, square, multiply by $x$, square, square, multiply by $x$, square, square, square. All told, 14 operations. After each operation, replace what you have by the remainder upon division by 153 --- that way, you never have to deal with numbers more than 5 digits long. So, after 14 multiplications, and 14 divisions-with-remainder by 153, no calculation involving a number of over 5 digits, you should get your answer.