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

cryptographymodular arithmetic

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.

Best Answer

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.

Related Question