Question

What is the remainder when ${128}^{1000}$ is divided by 153?

• A. 103
• B. 145
• C. 118
• D. 52

Answer 1

The correct option is D 52

We can solve this by splitting the denominator into two co-prime numbers 9 and 17. First find the remainder of ${128}^{1000}$ on division by 9.
${128}^{1000}÷9\to 2^{1000}÷9=(2^6{)}^{166}\times 2^4÷9\to Remainder=7$. This means that ${128}^{1000}$ is a 9n + 7 number.
Next find the remainder of ${128}^{1000}$ on division by 17.
${128}^{1000}÷17\to 9^{1000}÷17=\left[\right(9^{16}{)}^{62}\times 9^8]÷17\to Remainder=1$. This means that ${128}^{1000}$ is a 17n + 1 number. If we try to look for a number below 153, that is both 17n + 1 as well as 9n + 7, we would see that the number 52 fulfills this requirement. Hence, 52 is the required remainder of ${128}^{1000}÷153$