1
$\begingroup$

Knuth's up-arrow notation extends the concept of exponentiation in a recursive manner.

Euler's theorem can be restated in the arrow notation as: $a \uparrow \phi(m) \equiv 1 \mod m$, whenever $(a, m) = 1$. I was wondering what function $f_k(m)$ would ensure that $a \uparrow^k f_k(m) \equiv 1 \mod m$ and under what conditions can we ensure that such a $f_k(m)$ exists. It is elementary to note that, when $\phi(m) | a$, for all values $n, k >= 2$, we have: $a \uparrow^k n \equiv 1 \mod m$. I could neither find such a $f_k(m)$ nor prove that no such number exists when $\phi(m) \not | a$

As Euler's $\phi(n)$ doesn't always equal the order of $n$ in $m$, I'm only looking for a function $f_k(m)$ that ensures that $a \uparrow^k f_k(m)$ is congruent to $1$ modulo $m$ (under appropriate conditions); not necessarily the smallest such number.

Improve this question
$\endgroup$
6
  • $\begingroup$ It looks like $f_k(m) = 0$ is an answer to your question, but perhaps an unsatisfying one. Since this question is accumulating votes to close (but without much of an explanation), it might find a more welcome home at math.stackexchange.com $\endgroup$
    – S. Carnahan ♦
    Apr 3, 2011 at 16:47
  • $\begingroup$ It might be of interest to know how I came across this. I was trying to find the last d decimal digits of $a \uparrow \uparrow b$ and found a simple recurrence for $r_{i,j} \equiv a \uparrow \uparrow i \mod \phi_i (10^d)$ and we require $r_{b, 0}$, which solves the question when $(a, 10) = 1$. For finding the last digits of $a \uparrow^k b$ when $k > 2$, we require some sort of extension of Euler's theorem to reduce the large exponents to unity. $\endgroup$
    – quantumelixir
    Apr 3, 2011 at 19:08
  • $\begingroup$ However, I later found that the last $d$ decimal digits $a \uparrow^k b$ attain a fixed point and do not change further as the height of the tower increases. For instance, the last 500 digits of [Graham's number](en.wikipedia.org/wiki/Graham's_number) is computed noting this fact. This implies that the original motivating question on last digits of large numbers is rather un-interesting, unless of course $d$ is very large. $\endgroup$
    – quantumelixir
    Apr 3, 2011 at 19:17
  • 1
    $\begingroup$ Observation 1: if you iterate $(1+x)$,$(1+x)^{(1+x)}$, $(1+x)^{(1+x)^{(1+x)}}$ and so on you will observe, that the leading entries of the according taylor-series stabilize and the power series does not change in the leading terms. Observation 2: it is different, whether you iterate (mod some number) or whether you take the complete iterate (mod some number). Since the basic definition of tetration is still derived from the iteration-paradigm, it should explicitely noted, which procedure one takes here. $\endgroup$
    – Gottfried Helms
    Apr 3, 2011 at 21:58
  • $\begingroup$ Very nice. Your first observation might explain why the digits of a power tower eventually stabilize and do not change with further increase in the height. The procedure I'm referring to here is that of taking the complete iterate modulo a power of 10. There is an interesting phenomenon wherein you are able to use the other method you just referred to (iterating modulo the same power of 10) till you attain a fixed point. This fixed point is the same (except for small tower heights) as that obtained by the more difficult procedure of computing the complete iterate modulo the power of 10. $\endgroup$
    – quantumelixir
    Apr 3, 2011 at 23:05

1 Answer 1

Reset to default
1
$\begingroup$

Suppose that for a positive integer $m$, there exists a positive integer $a>1$ such that $(a,m)=1$ and $\mathrm{rad}(\mathrm{ord}_m(a))\not|a$. Then $f_2(m)>0$ does not exists.

(Here $\mathrm{ord}_m(a)$ is the multiplicative order of $a$ modulo $m$, and $\mathrm{rad}(n)$ is the radical of an integer $n$.)

Indeed, for any $n>0$, $a\uparrow^2 n = a\uparrow (a\uparrow^2 (n-1))$ and $\mathrm{ord}_m(a)\not|(a\uparrow^2 (n-1))$, implying that $a\uparrow^2 n\not\equiv 1\pmod{m}$.

Similarly, under the same conditions, $f_k(m)>0$ does not exist for all $k>2$.

Below $10^6$ only for $m=2$ and $m=3$, the anticipated $a$ does not exists. I believe such $a$ actually exists for all $m>3$.

UPD. Above I implicitly assumed that $a < m$. If we drop this restriction, the problem becomes completely trivial.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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