+26367 What is the residue of \(9^{2010}\), modulo \(17\) ?
\(\begin{array}{|rcll|} \hline && \mathbf{9^{2010} \pmod {17}} \\ &\equiv & \left(3^2 \right)^{2010} \pmod {17} \\ &\equiv & 3^{2\cdot 2010} \pmod {17} \\ &\equiv & 3^{4020} \pmod {17} \\ & & \boxed{ a^{\varphi(n)} \equiv 1 \pmod {n} \text{, if gcd(a,n)=1 } \\ 3^{\varphi(17)} \equiv 1 \pmod {17} \text{, gcd(3,17)=1 } \quad \varphi(17) = 16 \\ 3^{16} \equiv 1 \pmod {17} } \\ &\equiv & 3^{16\cdot 251+4} \pmod {17} \\ &\equiv & \left(3^{16} \right)^{251}3^4 \pmod {17} \\ &\equiv & \left(1 \right)^{251}3^4 \pmod {17} \\ &\equiv & 3^4 \pmod {17} \\ &\equiv & 81 \pmod {17} \\ &\equiv & \mathbf{13 \pmod {17}} \\ \hline \end{array}\)
