1. **State the problem:** We want to find the remainder when $289^{125}$ is divided by 27, i.e., compute $289^{125} \bmod 27$. 2. **Simplify the base modulo 27:** Since $289$ is large, reduce it modulo 27 first. $$289 \bmod 27 = 289 - 27 \times \lfloor \frac{289}{27} \rfloor = 289 - 27 \times 10 = 289 - 270 = 19$$ So, $289^{125} \equiv 19^{125} \pmod{27}$. 3. **Use Euler's theorem or find the totient:** Since 27 = $3^3$, the Euler's totient function $\varphi(27) = 27 \times (1 - \frac{1}{3}) = 18$. Euler's theorem states that if $\gcd(a, n) = 1$, then: $$a^{\varphi(n)} \equiv 1 \pmod{n}$$ Here, $\gcd(19, 27) = 1$, so: $$19^{18} \equiv 1 \pmod{27}$$ 4. **Reduce the exponent modulo 18:** $$125 \bmod 18 = 125 - 18 \times 6 = 125 - 108 = 17$$ So, $$19^{125} \equiv 19^{17} \pmod{27}$$ 5. **Calculate $19^{17} \bmod 27$ using repeated squaring:** - $19^1 \equiv 19 \pmod{27}$ - $19^2 = 361 \equiv 361 - 27 \times 13 = 361 - 351 = 10 \pmod{27}$ - $19^4 = (19^2)^2 = 10^2 = 100 \equiv 100 - 27 \times 3 = 100 - 81 = 19 \pmod{27}$ - $19^8 = (19^4)^2 = 19^2 = 10 \pmod{27}$ (from above) - $19^{16} = (19^8)^2 = 10^2 = 100 \equiv 19 \pmod{27}$ 6. **Combine powers to get $19^{17}$:** $$19^{17} = 19^{16} \times 19^1 \equiv 19 \times 19 = 361 \equiv 10 \pmod{27}$$ 7. **Final answer:** $$289^{125} \bmod 27 = 10$$ Thus, the remainder is 10.