What's the formula for the fixed point of a power tower of $2$s modulo $n$?

e.g., $n = 3$. Clearly, the powers of $2$ modulo $3$ alternate $2, 1$. The powers of $4$ modulo $3$ are all $1$s. So a power tower of $2$s modulo $3$ must get stuck on $1$. Of course this method is inefficient, as $n = 5$ already shows. Is there a formula, or at least a more efficient method?

p.s. I tried Mathematica’s FixedPoint function but got very confused on the syntax, like whether to do 2, # or #, 2.

Solutions Collecting From Web of "What's the formula for the fixed point of a power tower of $2$s modulo $n$?"

Thinking about this as a fixed point is a bit misleading, since $k \mapsto 2^k$ is not a well defined function from $\mathbb{Z}/n \to \mathbb{Z}/n$. However, you are right that the sequence $2$, $2^2$, $2^{2^2}$, … is eventually constant modulo $n$ for any $n$.

Proof by induction on $n$: Let $n = 2^k s$ for $s$ odd. By the Chinese remainder theorem, it is enough to prove that the sequence is eventually constant modulo $2^k$ and modulo $s$. The claim modulo $2^k$ is obvious — the sequence is eventually zero. For $s$ odd, since $GCD(2,s) =1$, the value of $2^x$ modulo $s$ is determined by $x$ modulo $\phi(s)$. By induction, the sequence is eventually constant modulo $\phi(s)$, so it is also eventually constant modulo $s$ and we are done. $\square$.

Here is a straightforward Mathematica implementation.

oddPart[x_] := If[OddQ[x], x, oddPart[x/2]];
powerOfTwo[x_] := If[OddQ[x], 1, 2*powerOfTwo[x/2]];
eventualValue[1] = 0;
eventualValue[n_] :=
   With[{s = oddPart[n], t = powerOfTwo[n]},
     ChineseRemainder[{PowerMod[2, eventualValue[EulerPhi[s]], s] , 0}, {s, t}]];

The command PowerMod[a,b,m] computes $a^b \bmod m$ in a way which is faster and more memory efficient than Mod[a^b,m]. Other potential optimizations which I haven’t implemented would be to memoize eventualValue, and to use bit shifting tricks to compute oddPart and powerOfTwo.

If $n$ is even, then there is no such value. For $n$ odd, you can use Carmichael’s Function (wich would be equivalent to Euler’s Totient for an odd $n$)