Prove that $11^{10^3} \equiv 1 \pmod{10^4}$ In trying to prove that $11^{10^3}\equiv 1 \pmod {10^4}$. I have tried to rewrite the expression so that I can use Fermats little theorem using exponentional rules. Also I know that $a^p \equiv a \pmod p$. But I just get stuck in a circular argument going back to the original expression proving nothing. I think this should be fairly easy to prove, I just cant figure it out.
I also plugged this into wolframalpha and I think in general that $11^{10^a} \equiv 1 \pmod {10^{a+1}}$.
 A: Maybe consider $(1+10)^{10^3} = \sum_{k=0}^{10^3} \binom{10^3}{k} 10^k = \sum_{k=0}^{3} \binom{10^3}{k} 10^k \mod 10^4$?
It is straightforward to verify by computation that $10^4 \mid \binom{10^3}{k} 10^k$ for $k=1,2,3$.
A: A generalized version of copper.hat's answer:
\begin{align}
11^{10^a}\pmod{10^{a+1}}&= (10+1)^{10^a}\pmod{ 10^{a+1}} = \left[\sum_{i=0}^{10^a}\binom{10^a}{i}10^i\right] \pmod{ 10^{a+1}} \\
&= \left[\sum_{i=0}^{a}\binom{10^a}{i}10^i\right] \pmod{ 10^{a+1}}\\
& = \left[1+\sum_{i=1}^{a}\frac{10^{i-1}(10^a-1)\ldots (10^a-i)}{i!}10^{a+1}\right] \pmod{ 10^{a+1}}\\
&= 1.
\end{align}
Here, the last step follows because $\frac{10^{i-1}(10^a-1)\ldots (10^a-i)}{i!}$ is an integer. To prove this, we note that $\binom{10^a}{i}=\frac{10^{a}(10^a-1)\ldots (10^a-i)}{i!}$ is an integer. The factors of $i!$ that are cancelled with the factors of $10^a$ are multiples of $2$ and $5$. Clearly, the largest divisor of $i!$ that cancels with $10^a$ is less than $2^{i-1}5^{i-1}=10^{i-1}$. Therefore, $\frac{10^{i-1}(10^a-1)\ldots (10^a-i)}{i!}$ is also an integer.
