4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Try using Euler's theorem and induct on $q$. $\endgroup$ – msinghal Aug 15 '15 at 15:36
  • 4
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Aug 15 '15 at 15:42
  • 2
    $\begingroup$ 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. $\endgroup$ – Peter Aug 15 '15 at 15:57
  • 3
  • 3
    $\begingroup$ See also How can I effectively compute tetration mod a? on mathoverflow. $\endgroup$ – J.-E. Pin Aug 15 '15 at 16:19
4
$\begingroup$

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.

$\endgroup$

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.