Euler's theorem for Tetration, Pentation, etc. (Superexponentiation) - MathOverflow

Euler's theorem for Tetration, Pentation, etc. (Superexponentiation)

2011-04-03T12:02:35Z

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.

Answer by Max Alekseyev for Euler's theorem for Tetration, Pentation, etc. (Superexponentiation)

2011-04-04T05:49:47Z

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.