I understand how to do modular arithmetic on numbers with large exponents (like $8^{202}$). However, I am having trouble understanding how to calculate something like:
$ 3^{3^{3^{3^3}}}$ mod 5
(that's 5 3's there). Can anyone help me understand how to get this started?
On
When dealing with tetration, numbers really go out of hand... I've never seen modular arithmetic operated on tetrated numbers..
$$3\uparrow\uparrow1 = 3^1$$ mod 5 on this yields 3 $$3\uparrow\uparrow2 = 3^3$$ mod 5 on this yields a 2 $$3\uparrow\uparrow3 = 3^{(3^3)} = 3^{27}$$ mod 5 on this (Online calc) yields a two as well. Problem is, calculators (Atleast the ones available online), aren't able to calculate after this.
You're asking $$(3\uparrow\uparrow5) mod (5) = 3^{3^{3^{3^3}}} mod (5) $$ This may be of interest...https://zbmath.org/?q=an:0535.03018&format=complete http://www.sciencedirect.com/science/article/pii/0898122183901141
You can also look at http://en.wikipedia.org/wiki/Euler%27s_totient_function; http://math.eretrandre.org/tetrationforum/showthread.php?tid=45 for some ideas.
I'm not much into Mod arithmetic; but the two articles I've provided may be of some help, as they directly deal with your doubts...
PS: Good question! Definite thumbs up.
By Fermat's Little Theorem, it suffices to look at the exponent modulo 4, so the problem reduces to finding $3^{3^{3^3}}$ modulo 4. But $3^{3^{3^3}} \equiv (-1)^{(-1)^{3^3}} \equiv (-1)^{-1} \equiv -1 \pmod 4$.
Thus $3^{3^{3^{3^3}}} \equiv 3^{-1} \equiv 2 \pmod 5$.
Edit: Fermat's Little Theorem tells us that for any prime $p$, we have $a^{p-1} \equiv 1 \pmod p$ for all $a \not \equiv 0 \pmod p$. So, in particular, $a^4 \equiv 1 \pmod 5$ provided $a \not \equiv 0 \pmod 5$, which is why we can reduce the exponent modulo 4.