# Evaluation of hard expression with repeated exponentiation and modulo

Assume we want to calculate

$$N = z^{1998000^{100^{10}}} \pmod{10^m}$$

where $$z, m$$ are known ($$z$$ can reach up to $$10$$ digits and let's assume that $$m$$ is around $$10$$).

According to similar questions, it seems that the usual method is to find a $$k$$ such that:

$$z^k \equiv 1 \pmod{10^m} \tag{1}$$

Then proceed with finding:

$$19988000^{100^{10}} \pmod{k}$$

For solving $$(1)$$, the only thing that comes to mind is Euler's generalization of Fermat's little theorem, but that carries the assumption that $$\text{gcd}(z,10^m) = 1$$, which is not generally known.

Can you suggest a way to solve $$(1)$$ and how would you proceed with finding $$N$$ from there?

First suppose $$\gcd(z,10^m)=1$$. Then we can take $$k=4\cdot 10^{m-1}$$, and $$19988000^{100^{10}} \pmod{k}$$ is clearly $$0$$, so $$N=1$$.
Now suppose, say, that $$z$$ is even and not divisible by $$5$$. Then $$N\equiv 0\pmod {2^m}$$; and to compute $$N\bmod 5^m$$, we can take $$k=4\cdot 5^{m-1}$$, so $$N\equiv 1\pmod{5^m}$$. Now you can use the Chinese Remainder Theorem to find $$N\pmod{10^m}$$.
The case when $$z$$ is an odd multiple of $$5$$ is similar.
• The case of $z$ being an even multiple of $5$ is trivial? – Paris Nov 10 '20 at 20:36
• @Paris: yes, because then it's a multiple of $10$ – TonyK Nov 10 '20 at 21:06