What is the remainder when 1009^109 is divided by 101? Thanks for help.
\(\begin{array}{|rcll|} \hline && 1009^{109} \pmod {101} \qquad &| \qquad 1009 \pmod {101} = -1 \\ &\equiv & (-1)^{109} \pmod {101} \qquad &| \qquad (-1)^{109}=-1\\ &\equiv & -1 \pmod {101} \\ &\equiv & 100 \pmod {101} \\ \hline \end{array}\)
mod(1009^1,101) = 100
mod(1009^2,101) = 1
mod(1009^3,101) = 100
mod(1009^4,101) = 1
mod(1009^5,101) = 100
...
mod(1009^109,101) = 100
.
What is the remainder when 1009^109 is divided by 101? Thanks for help.
\(\begin{array}{|rcll|} \hline && 1009^{109} \pmod {101} \qquad &| \qquad 1009 \pmod {101} = -1 \\ &\equiv & (-1)^{109} \pmod {101} \qquad &| \qquad (-1)^{109}=-1\\ &\equiv & -1 \pmod {101} \\ &\equiv & 100 \pmod {101} \\ \hline \end{array}\)