IteratedFunctions.com What Lies Beyond Exponentiation?

# Recurrance

Even with symbolic software, tetration or iterated exponentiation typically produces numbers to large to manipulate. One method to circumvent this limitation is to work with tetration using modulo arithmetic. Dr. Luttmann raised the following problem in his number theory course. Let $\alpha_0 = 0, \; \alpha_n = 3^{\alpha_{n - 1}}$, then $\alpha_1 = 1,\; \alpha_2 = 3,\; \alpha_3 = 27,\; \alpha_4 = 7625597484987$, and in general $\alpha_{n+1}=\,^n 3$. Prove that $\alpha_k \equiv 87 ( mod \; 100 )$ where $k \gt 2$.

 $^0 3$ $\equiv$ 1 $^1 3$ $\equiv$ 3 $^2 3$ $\equiv$ 27 $^3 3$ $\equiv$ 97484987 $^4 3$ $\equiv$ 739387 $^5 3$ $\equiv$ 60355387 $^6 3$ $\equiv$ 26595387 $^7 3$ $\equiv$ 195387 $^8 3$ $\equiv$ 4195387 $^9 3$ $\equiv$ 64195387 $^{10} 3$ $\equiv$ 64195387
Tetrates of 3 $( mod \; 10^8 )$

Looking at the table indicates that $\alpha_k \equiv 87 ( mod \; 100 )$ where $k \gt 2$.

In the tetrates of 3, the the k$^{th}$ least significant digit "freezes", recurring in all $\,^{n} 3$ where $n \geq k$. Consider how $3^{387}=3^{300} \cdot 3^{80} \cdot 3^7$. Several identities of the Euler Phi function $\varphi(n)$ will be helpful in showing how congruences occur with $1 \; ( mod \; 10^k)$ for higher powers of $3^{{10}^n}$. Let $a$ and $b$ be two positive integers that are coprime, they have no common divisors, $\gcd(a,b)=1$,then $a^{\varphi(b)} \equiv 1 \; ( mod \; b )$ For $m>1$, $\varphi(b^m)=b^{m-1} \varphi(b)$ When working in a base $b$, $a^{\varphi(b^m)} = a^{b^{m-1} \varphi(b)} = ( a^{\varphi(b)}) ^{b^{m-1}} \equiv 1 \; ( mod \; b^m )$ Note how $\varphi(100)=40, \varphi(1000)=400, \varphi(10000)=4000$. While the Euler Phi function assures that if $m = \varphi(n)$ then $a^m \equiv 1 \; ( mod \; n )$, the Carmicheal function $\lambda(n)$ gives the smallest value of $m=\lambda(n)$ such that $a^m=a^{\lambda(n)} \equiv 1 \; ( mod \; n )$ The Carmicheal function gives values of $\lambda(100)=20, \lambda(1000)=100, \lambda(10000)=500$. $3^7=2187 \equiv 87 \; ( mod \; 10^2 )$ $3^{\lambda(10^2)} = 3^{20} = 3486784401 \equiv 1 \; ( mod \; 10^2 )$ $3^{80} = (3^{20})^4 \equiv 1^4 \equiv 1 \; ( mod \; 10^2 )$ $3^{\lambda(10^3)} = 3^{100} \equiv 1 \; ( mod \; 10^3 )$ $3^{300} = (3^{100})^3 \equiv 1^3 \equiv 1 \; ( mod \; 10^3 )$ $3^{300} \cdot 3^{80} = 3^{380} \equiv 1 \; ( mod \; 10^2 )$ Therefore $3^7=2187$ determines the last two digits of $3^{387}$. $3^{387} = 3^{380} \cdot 3^7 \equiv 1 \cdot 3^7 \equiv 87 \; ( mod \; 10^2 )$

 $3^{10^{0}}$ $\equiv$ 3 $7^{10^{0}}$ $\equiv$ 7 $3^{10^{1}}$ $\equiv$ 59049 $7^{10^{1}}$ $\equiv$ 282475249 $3^{10^{2}}$ $\equiv$ 621272702107522001 $7^{10^{2}}$ $\equiv$ 691459636928060001 $3^{10^{3}}$ $\equiv$ 102768902855220001 $7^{10^{3}}$ $\equiv$ 141207731280600001 $3^{10^{4}}$ $\equiv$ 498105206552200001 $7^{10^{4}}$ $\equiv$ 549213512806000001 $3^{10^{5}}$ $\equiv$ 250669865522000001 $7^{10^{5}}$ $\equiv$ 205755128060000001 $3^{10^{6}}$ $\equiv$ 468478655220000001 $7^{10^{6}}$ $\equiv$ 419551280600000001 $3^{10^{7}}$ $\equiv$ 862786552200000001 $7^{10^{7}}$ $\equiv$ 395512806000000001

 Contact: daniellgeisler@gmail.com