Is the identity $a^n \equiv a^{n \mod m} \mod m$ true if m is a power of 10

Question

I stumbled on this code, which finds the last digits of a tetration: https://blog.dreamshire.com/project-euler-188-solution/. The code seems to imply that $a^n \equiv a^{n \mod m} \mod m$ and takes advantage of this property to avoid calulation very large numbers. This implies that if you are working with powers (mod 10^m) you only need to care about the last m digits of the exponent.
I tried a few examples with pythons pow() and it seems to hold, but i cant find a proof. *with m > 1.

Answer 1

Suppose $\,p = 2^{\large 2^{\Large k}}\!\!+1\,$ is a (Fermat) prime, e.g. $\,p=5\ (k=1)\,$ for the OP.

Then $\ a^{\large (2p)^{\large n}}\!\equiv 1\pmod{(2p)^n}\,$ if $\,\color{#0a0}{n\ge 2^k}\! = \log_2(p\!-\!1)\,$ and $\,(a,2p)=1\ $ since

$\!\bmod 2^n$ it's true by $\,\phi(2^n)\:=\: 2^{n-1}\mid\, (2p)^n,\,$ by Euler $\phi\,$ & $ $ MOR = modular order reduction.

$\!\bmod p^n$ it's true by $\,\phi(p^n)\! =\! 2^{2^{\large k}}\!p^{n-1}\mid (2p)^n\,$ by $\,\color{#0a0}{n\ge 2^k}\,$ with same justification as above.

Thus it's true mod their lcm $= (2p)^n$ by CCRT, so for $\,m\! =\! (2p)^n\,$ we have by MOR

$$\bbox[12px,border:1px solid #c00]{\bmod m\!:\,\ a^{m}\equiv 1\,\Rightarrow\, a^N\!\equiv a^{N\bmod m}}\qquad\qquad$$

Remark $ $ More generally see Carmichael's generalization of Euler's Theorem.

Answer 2

This is valid for $m=10^8$. Namely, if $\gcd(a,10)=1$ we have (Euler's theorem):

• $a^{2^7}\equiv 1\pmod{2^8}$ as $\varphi(2^8)=2^7$
• $a^{4\cdot 5^7}\equiv 1\pmod{5^8}$ as $\varphi(5^8)=4\cdot 5^7$

Now, because both $2^7$ and $4\cdot 5^7$ are factors of $m=10^8$ we have that $a^m\equiv 1\pmod{2^8}$ and $a^m\equiv 1\pmod{5^8}$, so $a^m\equiv 1\pmod m$.

From this your statement follows fairly simply, but note that this is only valid for this very special modulus $10^8$, though the same proof would apply to all other powers of $10$, excluding $10$ itself. This is certainly not valid for a lot of other modules, as you have seen from the comments.