Leaning Tower Of Threes

Relevant wiki: Finding the last few digits of a power

Method 1 : Repeated use of Euler's totient function .

Let $^n a$ denote the Tetration function, $\Large ^n a = \underbrace{a^{a^{a^{\cdot^{\cdot^{\cdot^a}}}}}}_{n\text { times}}$ for positive integer $n$ . So we want to evaluate $^{2012} 3\bmod{100}$ .

Notice that the tetration function satisfy the condition that $\large ^n a = a^{\left( ^{n-1} a \right)}$ . So we have $\large ^{2012} 3 = 3^{^{2011}3}$ .

For simplicity sake, let $A = ^{2012} 3, \ B = ^{2011} 3, \ C = ^{2010} 3, \ D= ^{2009} 3, \ E = ^{2008} 3,\ F = ^{2007} 3,$ then $A = 3^B, B = 3^C , C = 3^D, D = 3^E, E = 3^F$ .

Since the greatest common divisor of 3 and 100 is 1, so we can apply Euler's totient function for modulo 100:

$\Large A \equiv 3^B \equiv 3^{B \; \bmod{\phi(100) }} \equiv 3^{B \; \bmod{40} } \equiv 3^{\color{#3D99F6}{3^C \; \bmod{40}}} \; \pmod{100}$

Likewise, since $\gcd(3,40) = 1$ , we can calculate the congruence (highlighted in blue) by applying Euler's totient function once more for modulo 40:

$\Large 3^C \equiv 3^{3^D \; \bmod{\phi(40)}} \equiv 3^{\color{#20A900}{3^D \; \bmod{16}}} \; \pmod{40}$

Likewise, since $\gcd(3,16) = 1$ , we can calculate the congruence (highlighted in green) by applying Euler's totient function once more for modulo 16:

$\Large 3^D \equiv 3^{3^E \; \bmod{\phi(16)}} \equiv 3^{\color{#D61F06}{3^E \; \bmod{8}}} \; \pmod {16}$

Likewise, since $\gcd(3,8) = 1$ , we can calculate the congruence (highlighted in red) by applying Euler's totient function once more for modulo 8:

$\Large 3^E \equiv 3^{3^F \; \bmod{\phi(8)} }\equiv 3^{3^F \; \bmod{4} }\equiv 3^{(-1)^F \; \bmod{4} }\equiv 3^{(-1)^\text{some odd number} \; \bmod{4} } \equiv 3^{-1} \equiv 3^3 \equiv 3$

So the expression in red is equal to 3, and sustituting these values back shows that
the expression in green is equal to $3^3 \bmod{16} = 11$ ,
the expression blue is equal to $3^{11} \bmod{40} = 27$ ,
and finally $A$ modulo 100 is $3^{27} \bmod{100} = \boxed{87}$ .

---

Method 2 : Repeated use of Carmichael's lambda function .

It's easy to show that $\lambda(100) = 20$ and $\lambda(20) = 4$ .

Since $\gcd(3,100) = 1$ , we can apply Carmichael's lambda function.

Using the same variables in Method 1, for modulo 100:

$\Large A \equiv 3^B \equiv 3^{B \; \bmod{\lambda(100)}} \equiv 3^{\color{#69047E}{B \; \bmod{20}}} \pmod{100}$

Likewise, since $\gcd(3,20) = 1$ , we can calculate the congruence (highlighted in purple) by applying Carmichael's lambda function. once more for modulo 20:

$\Large 3^B \equiv 3^{3^C \; \bmod{\lambda(20)} }\equiv 3^{3^C \; \bmod{4} }\equiv 3^{(-1)^C \; \bmod{4} }\equiv 3^{(-1)^\text{some odd number} \; \bmod{4} } \equiv 3^{-1} \equiv 3^3 \equiv 7 \pmod{20}$

So the expression in purple is equal to 7, and substituting these values back shows that $A$ modulo 100 is $3^{7} \bmod{100} = \boxed{87}$ as well.

---

Food for thought : What is the last few digits of Graham's number ? Coincidence?

Note that $3^2 \equiv 1 \pmod {4}$ , $3^4 \equiv 1 \pmod {5}$ and $3^{20} \equiv 1 \pmod {25}$ , so that $3^{20} \equiv 1 \pmod {100}$ and $3^{4} \equiv 1 \pmod{20}$ . If we define $X(n) \; = \; \underbrace{3^{3^{3^{\cdot^{\cdot^{\cdot^{3^3}}}}}}}_{\times n}$ then $X(2010) \; = \; 3^{X(2009)} \; \equiv \; (-1)^{X(2009)} \; \equiv \; -1 \; \equiv \; 3 \pmod{4} \;,$ so that $X(2011) \; = \; 3^{X(2010)} \; \equiv \; 3^3 \; \equiv \; 7 \pmod{20} \;,$ and hence $X(2012) \; \equiv \; 3^{X(2011)} \; \equiv \; 3^7 \; \equiv \; 87 \pmod{100} \;.$