# Modular Arithmetic and repeated exponentiation

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?

• For example, $2^{2^{2}} = 2^4 = 16 \equiv 2 \pmod 7$, $2^2 \equiv 4 \pmod 7$ – dust05 May 31 at 10:26
• Well, it seems to work in some specific cases so, when is it true? Since it seems to work for 40, 3 and 7, for a while at least, and 50, 7 and 8. There seem to be cases where it is true. I'll add on an additional edit taking this into account. – Anthony P May 31 at 10:34
• $(50, 7, 8)$ case can be also explained; $50^7 = 2^7 \cdot N$ for some $N$ integer, and $8 | 2^7$ so they are all 0 $\pmod 8$. – dust05 May 31 at 10:40

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. 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:

$$a^{P_n(k)}\bmod b$$ is eventually constant in $$k$$. What you are observing is the special case when it starts being constant at $$k=1$$.

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$$.

Note that $$40 \equiv 5 \pmod7$$, and $$5^6 \equiv 1 \pmod 7$$. (Fermat)

Each of $$3$$, $$3^3$$, $$3^{3^3}, \cdots$$ are multiple of $$3$$ and is not even, so they are all of the form $$6k+3$$. This leads to $$40^{3^{3^\cdots}} \equiv 5^3 \equiv 6 \pmod 7$$.

I think one could find more pattern like this; Let $$b$$ odd prime, $$n = (b-1)/2$$, $$a$$ be comprime to $$b$$.

• This question originally sprouted from the fact that $3^{3^{\cdots}}$ is congruent to less iterated powers under mod $10^k$, where $k$ is the $k$ in $P_n(k)$, can something be done for this as well? Sorry, I understand your argument but I don't really get how to extend it to other cases. In other words all $3^[P_3(m)}$ has the same $k$ digits as $3^{P_3{k}}$, where $m \geq k$ – Anthony P May 31 at 10:50
• I'm sorry; odd condition is not sufficient. $b$ should be prime of the form $4k+3$. With this (additional) condition we can proceed with same steps; $n^{n^\cdots}$ is odd and is multiple of $n$. so it is congruent with $n \pmod{b-1}$. $a^{b-1} \equiv 1 \pmod {b}$ by Fermat Little theorem. – dust05 May 31 at 10:55
• Let me think of the explation with $10^k$ thing. – dust05 May 31 at 10:57
• This is also explained as follows; the following $5^{10} = 5^{100} = 5^{1000} = \cdots \equiv 2\pmod7$ holds. $5^{10..0} = 5\cdot 5^{9..9} = 5\cdot 5^{6k + 3}$ for some integer $k$. And again $5^6 \equiv 1\pmod 7$. – dust05 May 31 at 11:06
• I don't quite understand how this explains the $10^k$ thing? – Anthony P May 31 at 11:14