What are the last 2 digits of $31^{41}$? By using a slick trick, I found that the last two digits were $31.$ However, I want to verify this using Fermat's little theorem or some alternate. How would I apply Fermat's Little Theorem?
 A: Since $\phi(100) = 40$ we have by Euler theorem $$31^{40}\equiv 1 \pmod{100}$$
So the answer is $31$.
A: Note that 
$$
a^{\varphi(100)}=1
$$
where $\varphi$ is the Euler totient function. 
$$
\varphi(100)=\varphi(2^2)\varphi(5^2)=2(20)=40
$$
since it is multiplicative on relatively prime numbers. Note also that 
$$
\varphi(p^2)=p(p-1)
$$
it is now easy to conclude.
A: John Watson's approach is what I would go with, but to add an alternative, we can raise $31^{41}\pmod{100}$ using the Square and Multiply Algorithm. First, note that $41=101001_{\text{two}}$
$$
\begin{array}{r|r|rl}
n&\text{base two}&31^n\pmod{100}\\
0&0&1\\
1&1&31&\text{multiply}\\
2&10&61&\text{square}\\
4&100&21&\text{square}\\
5&101&51&\text{multiply}\\
10&1010&1&\text{square}\\
20&10100&1&\text{square}\\
40&101000&1&\text{square}\\
41&101001&31&\text{multiply}
\end{array}
$$
A: You changed the problem on me after I answered. So:
Two find the last two digits, just work in $\mathbb Z\bmod100.$
\begin{align}
33^1 & \equiv 31 \\
31^2 & \equiv 31\times 31 \equiv 61 \\
31^3 & \equiv 31\times61 \equiv 91 \\
31^4 & \equiv 31\times91 \equiv 21 \\
31^5 & \equiv 31\times21 \equiv 51 \\
31^6 & \equiv 31\times51 \equiv 81 \\
31^7 & \equiv 31\times81 \equiv 11 \\
31^8 & \equiv 31\times11 \equiv 41 \\
31^9 & \equiv 31\times41 \equiv 71 \\
31^{10} & \equiv 31\times71 \equiv 1
\end{align}
Therefore
$$
31^{41} = 31^{10}\times31^{10}\times31^{10}\times31^{10}\times31^1 \equiv 1\times1\times1\times1\times31 \equiv 31.
$$
Two find the last two digits, just work in $\require{cancel}\xcancel{\mathbb Z\bmod100.}$
$$
\xcancel{
\begin{align}
32^1 & \equiv 32 \\
32^2 & \equiv 32\times 32 \equiv 24 \\
32^3 & \equiv 32\times24 \equiv 68 \\
32^4 & \equiv 32\times68 \equiv 76 \\
32^5 & \equiv 32\times76 \equiv 32
\end{align}}
$$
After five steps you're back to $32.$
Every time you go four steps beyond where you had $32,$ you have $32$ again. So $41 = 1 + (1\times4)$ so you go through that cycle $10$ times, getting back to $32.$
A: Hint:
$$(1+10n)^m\equiv1+\binom m1(10n)^1\pmod{100}$$
Now, $41\cdot3\equiv3\pmod{10}$
$\implies41\cdot30\equiv30\pmod{100}$
