# Infinite exponentiation $n^{n^{n^{…^n}}} \equiv m \pmod q$ , find m?

let $(n,q) \in \mathbb N^{*^2}$

I was wondering if it was possible to find a function $f_q$ such that :

$f_q(n)=m$ where $m$ is such that $n^{n^{...^n}} \equiv m \mod q$

or at least an easy way to find m, where $n^{n^{...^n}}$ denotes "infinite" exponentiation, assuming of course it has a "limit" if you see what I mean (that's to say, if you exponentiate long enough, $n^{n^{n^{...^n}}} \equiv m \mod q$, m becomes constant. Is it always the case ? I don't know, but it has to be at least periodic since m belongs somewhere between $0$ and $q-1$... so it has to repeat itself after some exponentiations) To make things easier, let's only consider n for which $n^{n^{n^{...^n}}}$ tends to $m \mod q$ constant

I have made some trials and it seems like it often has a "limit" ($m$ constant)

For example, $f_{10}(7)=3$ since :

$7^7 \equiv 49*49*49*7 \equiv 9*9*9*7 \equiv 81*63 \equiv 3$ mod 20

$7^{3+20k} \equiv 343*(343*343*343*7)^{2k} \equiv 3*(3*3*3*7)^{2k} \equiv 3*81^k \equiv$ 3 mod 20

So $7^{7^{...^7}} \equiv 3$ mod 20, and of course $\equiv 3$ mod 10

I have done this for other numbers, and could provide them with proof but it's a very exhausting process when n becomes big and I couldn't find any obvious pattern...

Sorry if the explanation is a bit messy, the maths I am trying to do isn't very conventional... and probably not very useful either, but I'm still curious... If additional explanation is needed, I'll just edit and add some information

Thanks a lot for anyone ready to help me tackle this not-so-easy arithmetic problem... To be honest I don't think there is a general solution, but I'd be very grateful if someone could find f for even a small subset of $N$.

• Try using Euler's theorem and induct on $q$. – msinghal Aug 15 '15 at 15:36
• One tricky problem here is that exponentiation is not really a modular operation in the exponent place; we generally have $a^b\bmod q \ne a^{b\bmod q}\bmod q$. So the naive argument that you always reach a period doesn't seem to work. – Henning Makholm Aug 15 '15 at 15:42
• For natural numbers $a,n$, there is a number $k$, such that $a\uparrow \uparrow m \equiv a\uparrow \uparrow k$ (mod $n$). for all $m\ge k$. So, the sequence of residues becomes eventually stationary. You can reduce the base modulo $n$, the first exponent modulo $\phi(n)$, the second exponent modulo $\phi(\phi(n))$ and so on. But the calculation is not easy in general, especially for high modules. – Peter Aug 15 '15 at 15:57
• – J.-E. Pin Aug 15 '15 at 16:15
• See also How can I effectively compute tetration mod a? on mathoverflow. – J.-E. Pin Aug 15 '15 at 16:19

Yes, this is always possible, though it's not necessarily trivial to prove. Let's start with the easier case: assume $n$ and $q$ are coprime. Then, the following identity defines $f_q(n)$ uniquely (mod $q$): $$f_q(n)\equiv n^{f_{\phi(q)}(n)}\pmod q$$ where $\phi(q)$ is Euler's totient function, equaling the number of integers between $0$ and $q$ which are coprime to $q$. For instance, to obtain $f_{10}(7)=3$ using this, we note that $\phi(10)=4$ and $\phi(4)=2$ and $\phi(2)=1$ and then using the recursion (noting that $f_1$ is define mod $1$, so can be chosen arbitrarily): $$f_1(7)\equiv 0$$ $$f_2(7)\equiv 7^0\equiv 1$$ $$f_4(7)\equiv 7^1 \equiv 3$$ $$f_{10}(7)\equiv 7^3 \equiv 3$$ Since that function is decreasing, applying the second identity finitely many times eventually reduces to $q=1$. Notice, as rough bound on how many exponents we need, we can say $$f_{q}(n)=\underbrace{n^{n^{n^{\ldots ^{n}}}}}_{q\text{ times}}$$ but this is much harder to computer than just using the recurrence relation.
The crucial fact used here is that, for any $q$ and large enough $k$, the following is true: $$a^k\equiv a^{k+\phi(q)}\pmod q$$ meaning exponentiation is eventually periodic, with period $\phi(q)$, so knowing the infinite power tower's value mod $\phi(q)$ suffices to determine it mod $q$. The nicest proof of this fact I know is that the integers coprime to $q$ taken mod $q$ form a group under multiplication of order $\phi(q)$ and $\{a^0,a^1,a^2,\ldots,\}$ is a subgroup thereof so its order $k$ divides $\phi(q)$ due to Lagrange's theorem. This implies $a^k=a^0$ and hence $a^{\phi(q)}=a^0$, which implies the desired result. One may notice that a similar thing works when $n$ is not coprime to $q$ - exponentiation $n^x$ is still eventually periodic mod $q$. One may prove, as a loose bound, that if $x>\log_2(q)$ then $n^{x}\equiv n^{x+\phi(q)}\pmod{q}$, which allows us to compute $f$ in a similar manner as long as the representative we choose of $f_{\phi(q)}(n)$ mod $\phi(q)$ is big enough.