elementary number theory - Calculating $2^{9999 }$ mod $100$ using Fermats little Theorem

By a modified version of the Fermat's little theorem we obtain that $a^{\phi(n)} \equiv 1$ mod $n$ whenever $(a,n)=1$. But my professor accidentally gave this question to calculate $2^{9999 }$ mod $100$. So everyone in the class calculated it using the theorem since they forgot to check that $(a,n)=1$. But to my surprise everyone got $88$ as the answer which is actually the correct answer.

So I first saw what happens in the case of mod $10$. Here $2^4 \equiv 6$ mod $10$. But magically enough this number multiplies with powers of $2$ as if it were identity i.e.

$$2\cdot6 \equiv 2 \pmod {10}$$

$$4\cdot6 \equiv 4 \pmod {10}$$

$$6\cdot6 \equiv 6 \pmod {10}$$

$$8\cdot6 \equiv 8 \pmod {10}$$

After seeing this I checked what happens in the case of $100$. Similar thing happens even here instead $2^{40} \equiv 76\pmod{100}$. Now $76$ acts like $6$ just that $76*2 \neq 2$ but otherwise $76*4=4$ and $76*8=8$ and so on. Can anyone explain as to why it is happening here and does it happen in other cases as well.

Answer

What's going on here is a direct result of the prime factorizations of $10 = 2\cdot 5$ and $100 = 2^2\cdot 5^2$. Try writing it like this:

$$\begin{align*} 2\cdot 6\equiv 2\cdot(5+1)&\equiv 2\cdot 5 + 2\cdot 1\equiv 0 + 2\pmod{10}\\ 4\cdot 6&\equiv4\cdot 5 + 4\cdot 1\equiv 0 + 4\pmod{10} \end{align*}$$
and so on. Since $6 = 5+1$, multiplying by an even number will "cancel out" the $5$, and you'll just be left with the $1$, acting like an identity. Same thing is going on with $76 = 75 + 1 = 3\cdot 25 + 1$. To cancel out the $3\cdot 25$, you need an even number that's divisible by $4$ ($4\cdot 25 = 100$). If you test $76\cdot 6\pmod{100}$, you should find that the result is nonzero.

This sort of thing will happen whenever you're calculating mod $n = \prod_{i = 1}^m p_i^{e_i}$ (here $\prod_{i = 1}^m p_i^{e_i}$ is the prime factorization of $n$) and you look at multiplication by a number $k$ of the form $1 + (\textrm{anything})(\textrm{product of some of the }p_i\textrm{'s})$. Whenever you multiply $k$ by any number whose factorization includes the $p_i$'s not appearing in the "product of some of the $p_i$'s" (counted with multiplicity), you'll cancel off the second term of $k$ and be left essentially multiplying by $1$. As an easy example, look mod $6$. Multiplication by $3$ acts like the identity for $3$ and $0$ because $3 = 1 + 2$ and $6 = 2\cdot 3$.