# 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.

• Hint: $2^{9999}\equiv 0\pmod 4$. So you only need to solve $2^{9999}\pmod {25}$, and then solve the Chinese Remainder Theorem question. – Thomas Andrews Jan 20 '15 at 4:38
• @ThomasAndrews $2^{20} \equiv 1 \pmod{25}$ So using that I solved it but I was amazed at how $76$ acted like $1$ and I want to know whether it happens with other numbers as well – happymath Jan 20 '15 at 4:41
• To comment on the pattern you noticed: $6 = 5+1$, and $10 = 2\cdot 5$. So for any even number $n$: $6\cdot n\equiv 5\cdot n + 1\cdot n\equiv 0 + n\equiv n\pmod{10}$. $76$ behaves in a similar way because $76 = 75+1 = 3\cdot 25 + 1$ and $100 = 4\cdot 25$. If you multiply $76$ by a number divisible by $4$, it'll cancel off the $3\cdot 25$, but multiplying by even numbers that aren't divisible by $4$ doesn't cancel it completely (try $6$). – Stahl Jan 20 '15 at 4:42
• @Stahl thanks so when all can I do this kind of a trick? – happymath Jan 20 '15 at 4:43
• I'll add a comment about that to the answer I just wrote up. – Stahl Jan 20 '15 at 4:44

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$.
If $x\equiv 1\pmod{5^k}$, then $x\cdot (2^ka)\equiv 2^ka\pmod{10^k}$ for any integer $a$.
That's because $2^kax-2^ka=2^ka(x-1)$ is divisible by $2^k$ and by $5^k$, hence divisible by $10^k$.
More generally, if $x\equiv 1\pmod {m}$ then $x(nk)\equiv nk\pmod{mn}$ for any $n,k$.