1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ For example, $2^{2^{2}} = 2^4 = 16 \equiv 2 \pmod 7$, $2^2 \equiv 4 \pmod 7$ $\endgroup$ – dust05 May 31 at 10:26
  • $\begingroup$ 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. $\endgroup$ – Anthony P May 31 at 10:34
  • $\begingroup$ $(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$. $\endgroup$ – dust05 May 31 at 10:40
1
$\begingroup$

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:

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

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Anthony P May 31 at 10:50
  • $\begingroup$ 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. $\endgroup$ – dust05 May 31 at 10:55
  • $\begingroup$ Let me think of the explation with $10^k$ thing. $\endgroup$ – dust05 May 31 at 10:57
  • $\begingroup$ 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 $. $\endgroup$ – dust05 May 31 at 11:06
  • $\begingroup$ I don't quite understand how this explains the $10^k$ thing? $\endgroup$ – Anthony P May 31 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.