Compute remainder of division

Question

I am trying to compute the remainder of the following division:

$$9^{123456789} \quad\textrm{by}\quad 17.$$

Any ideas on how to work this out?

Answer 1

$9^n$ is a periodic sequence modulo 17 (Fermat's little theorem says that $9^{17} \simeq 9 \mod 17$).

Thus take the reminder $r$ of 123456789 by 17.

$$r \simeq 123456789 \mod 17$$

Then, because $(9^n \mod 17)$ is 17-periodic, we have

$$9^{123456789} \simeq 9^r \mod 17$$

Answer 2

we have $123456789=3^2\cdot 3803\cdot 3607$ thus we get $9^9\equiv 9 \mod 17$ and $9^{3803}\equiv 15 \mod 17$ and $15^{3607}\equiv 8 \mod 17$ thus we have $9^{123456789} \equiv 8 \mod 17$