Euler's theorem for Tetration, Pentation, etc. (Superexponentiation) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T21:19:50Z http://mathoverflow.net/feeds/question/60429 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60429/eulers-theorem-for-tetration-pentation-etc-superexponentiation Euler's theorem for Tetration, Pentation, etc. (Superexponentiation) quantumelixir 2011-04-03T12:02:35Z 2011-05-02T06:22:14Z <p>Knuth's <a href="http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation" rel="nofollow">up-arrow notation</a> extends the concept of exponentiation in a recursive manner.</p> <p>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$</p> <p>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.</p> http://mathoverflow.net/questions/60429/eulers-theorem-for-tetration-pentation-etc-superexponentiation/60523#60523 Answer by Max Alekseyev for Euler's theorem for Tetration, Pentation, etc. (Superexponentiation) Max Alekseyev 2011-04-04T05:49:47Z 2011-04-04T05:58:14Z <p>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.</p> <p>(Here $\mathrm{ord}_m(a)$ is the <a href="http://en.wikipedia.org/wiki/Multiplicative_order" rel="nofollow">multiplicative order</a> of $a$ modulo $m$, and $\mathrm{rad}(n)$ is the <a href="http://en.wikipedia.org/wiki/Radical_of_an_integer" rel="nofollow">radical of an integer</a> $n$.)</p> <p>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}$.</p> <p>Similarly, under the same conditions, $f_k(m)>0$ does not exist for all $k>2$.</p> <p>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$.</p> <p>UPD. Above I implicitly assumed that $a &lt; m$. If we drop this restriction, the problem becomes completely trivial.</p>