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