What is the residue of $9^{2010}$, modulo 17?
We start by generating powers of 9 modulo 17. Note that we can generate $9^{2k}$ from $9^k$ by squaring $9^k$. We get \begin{align*}
9^1 &\equiv 9 \pmod{17} \\
9^2 &\equiv 13 \pmod{17} \\
9^4 &\equiv 16 \pmod{17} \\
9^8 &\equiv 1 \pmod{17}.
\end{align*}Since $9^8 \equiv 1$ modulo 17, we have \begin{align*}
9^{2010} &\equiv 9^2 9^{2008} \\
&\equiv 9^2 (9^8)^{251} \\
&\equiv 9^2 1^{251} \\
&\equiv 9^2 \\
&\equiv \boxed{13} \pmod{17}.
\end{align*}
13
Level 5
Number Theory
Problem: What is the residue of $9^{2010}$, modulo 17?
Solution:<|START_OF_LATENT|><|PRIOR_PREFIX|>To find the residue of $9^{2010}$ modulo 17, we can utilize Fermat's Little Theorem, which states that if $p$ is a prime and $a$ is an integer not divisible by $p$, then $a^{p-1} \equiv 1 \mod p$. Here, $p = 17$ and $a = 9$. Since 9 is not divisible by 17, we can apply the theorem.

First, we calculate $p - 1 = 17 - 1 = 16$. According to Fermat's theorem, we have:

$9^{16} \equiv 1 \mod 17$.

Next, we need to reduce the exponent 2010 modulo 16 to simplify the calculation of $9^{2010}$. We compute:

$2010 \mod 16$.

To do this, we divide 2010 by 16:

$2010 \div 16 = 125$ remainder $10$.

Thus, $2010 \equiv 10 \mod 16$. This means we can replace $9^{2010}$ with $9^{10}$ modulo 17:

$9^{2010} \equiv 9^{10} \mod 17$.

Now, we need to compute $9^{10} \mod 17$. We can do this by first calculating lower powers of 9 modulo 17:

$9^1 \equiv 9 \mod 17$.

$9^2 = 81 \equiv 13 \mod 17$ (since $81 - 4 \times 17 = 13$).

$9^4 = (9^2)^2 \equiv 13^2 = 169 \equiv 16 \mod 17$ (since $169 - 9 \times 17 = 16$).

$9^8 = (9^4)^2 \equiv 16^2 = 256 \equiv 1 \mod 17$ (since $256 - 15 \times 17 = 1$).

Now we can express $9^{10}$ as:

$9^{10} = 9^8 \cdot 9^2 \equiv 1 \cdot 13 \equiv 13 \mod 17$.

Thus, the residue of $9^{2010}$ modulo 17 is $13$.<|END_OF_LATENT|> The final answer is $13$.