0
$\begingroup$

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?

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The case of $z$ being an even multiple of $5$ is trivial? $\endgroup$ – Paris Nov 10 '20 at 20:36
  • $\begingroup$ @Paris: yes, because then it's a multiple of $10$ $\endgroup$ – TonyK Nov 10 '20 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.