I was messing around with mod and repeated exponentiation and noticed that if we let $P_n(k)$ denote repeated exponentiation by $n$, $k$ times then,
$$\text{mod} \ b : a^{P_n(k)} \equiv a^{P_n(k-1)} \equiv a^{P_n(k-2)} \equiv \cdots \equiv a^{P_n(1)}=a^n.$$
Which however, isn't true if I let $k$ go to $0$.
For example,
$$\text{mod} \ 7 : 40^{3^{3^{3^{3}}}} \equiv 40^{3^{3^3}} \equiv 40^{3^3} \equiv 40^3 \equiv 6$$
Is this true in general? For any values of $a,b,n,k$ for which it is defined? I tried proving this by induction but was unsuccessful, but if possible it is preferable that the proof is not done by induction since induction doesn't exactly explain $\textbf{why}$ something is true.
EDIT: Noticing a couple of cases where it isn't true namely in the comments, I edit my question to.
For which $a,b,n,k$ is this true?
Best Answer
First of all, one can see that $a^n\bmod b$ is eventually periodic in $n$. Let $a^{n+b'}\equiv a^n$ for sufficiently large $n$. Then the problem boils down to finding $n\bmod b'$.
By similar arguments, one can furthermore show that $n^k\bmod b'$ is eventually periodic in $k$ for $k<b'$. By induction, this let's us push a $\bmod$ up the power tower, until eventually we reach $\bmod1$, which gives us $0$. At such a point, additional powers only contribute to reaching the point where we reach that "eventually periodic" step.
Conclusion:
Additional note:
Euler's totient and Carmichael's functions gives a $\bmod$ that gets pushed up into the next power (although it may not be optimal), so repeatedly applying $\varphi$ or $\lambda$ to the initial $b$ gives you a maximum height to check. For example, when $b=7$ and with Euler's totient function, we have
$\varphi(7)=6$
$\varphi(6)=2$
$\varphi(2)=1$
which means we only have to manually check $k<3$. For $a=40$ and $n=3$, it happens to be the case, so it holds for all $k\ge1$.