Question:
Which of the numbers $0,1,2, ..., 60$ is $10 ^ {60 \cdot 2 ^ {100} +2}$ congruent with modulo $61$?
How should you think about this? I know that you should think think that you should break it out a little more like $x ^ {a * b} = (x ^ b) ^ a$ use modolo in the parentheses, so as to always get smaller parts of the number as far as possible, etc, etc. .
But be a little thoughtful if that's how you should do it. also have the idea that you can put all numbers in a list, up to mod 60, and see which numbers are congruent.
But since 61 is the quite high number, it feels excluded.
Also $10 ^ {60 * 2 ^ {100} +2}$ is also a large number.
So need a little push
Fermat's Little Theorem asserts that if $p$ is a prime that does not divide $a\in\mathbb{Z}$, then $a^{p-1}\equiv1\pmod{p}$. With $p=61$ and $a=10$, we have $$10^{60}\equiv1\pmod{61}$$ Therefore, $$10^{60\cdot2^{100}+2}\equiv(10^{60})^{2^{100}}\cdot10^2\equiv1\cdot10^2\equiv39\pmod{61} $$