This question follows up on an example from brilliant.org

Look at the example of finding the last three digits of $4^{2^{42}}$

Euler's totient function is used, but I think incorrectly so I want to clear my doubts. The author uses it for reducing the exponent. Concretely this is the issue:

$2^{42} \equiv 2^2 \equiv 4$ (mod 100)

How is it possible to use Euler's theorem to reduce this exponent if $2$ and $100$ are not coprime?

  • $\begingroup$ Indeed, even though $\varphi(100)=40$ we have $2^{40}\equiv 76\pmod {100}$. Still, it's not hard to verify that $2^{42}\equiv 4 \pmod {100}$. $\endgroup$ – lulu Jan 22 '19 at 20:05
  • $\begingroup$ I know it is easy to verify, but the point is not to use a calculator and I was trying to understand how can that be usage of Euler's theorem so I did not use CRT. So you agree it is an error? $\endgroup$ – Michael Munta Jan 22 '19 at 20:22
  • 1
    $\begingroup$ Shouldn't need a calculator. $\varphi(25)=20$ so $2^{40}\equiv 1 \pmod {25}$ so $2^{42}\equiv 4\pmod {25}$. Clearly $2^{42}\equiv 0 \pmod 4$ and the chinese remainder theorem immediately settles the point. $\endgroup$ – lulu Jan 22 '19 at 20:27
  • $\begingroup$ Not sure I'd call what they wrote an error, though I'd agree it was unhelpfully terse. Euler's Theorem is the way to go here. You just have to realize that you should apply it to $25$, not $100$. $\endgroup$ – lulu Jan 22 '19 at 20:28

$100 = 2^2 \cdot 5^2$, so any value mod $100$ depends on that value mod $2^2$ and mod $5^2$. Mod $2^2$ is easy: $2^j \equiv 0 \mod 2^2$ if $j \ge 2$. Mod $5^2$ you use Euler.

  • $\begingroup$ Yes, I did not see that. It is confusing because in the article the author does not show this and says that Euler's theorem was used which I think is an incorrect usage because $2$ and $100$ are not coprime. $\endgroup$ – Michael Munta Jan 22 '19 at 20:13

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.