Given an infinite sequence $a_1, a_2, \dots$ where all $a_i > 1$ we study $a_1^{\,a_2^{\,\cdots}} \bmod m$. While this is an infinite power tower that grows without bound, I argue that it can be assigned a value. If $f(n)$ is the power tower with the first $n$ terms of $a$, there is a constant $c$ such that $f(n) \equiv f(c) \mod m$ for all $n > c$. In a sense the power tower converges modulo $m$. An explicit algorithm to compute this remainder is as follows:

  1. If $(a_1 \bmod m) \leq 1$, we have $a_1^{\,a_2^{\,\cdots}} \equiv a_1 \mod m$.

  2. Otherwise, factor $m$ into primes $p_i$. We calculate $\displaystyle x = \prod_{\gcd(p_i, a) = 1} p_i$ and $y = m/x$.

    Then, we compute $a_1^{\,a_2^{\,\cdots}}\bmod x$ and $a_1^{\,a_2^{\,\cdots}}\bmod y$ and use the Chinese remainder theorem to find $a_1^{\,a_2^{\,\cdots}}\bmod xy = a_1^{\,a_2^{\,\cdots}}\bmod m$.

    Since $a_1$ and $x$ are coprime we have $a_1^{\,a_2^{\,\cdots}}\equiv a_1^{\,a_2^{\,\cdots} \bmod \phi(x)} \mod x$. We recursively compute $r = a_2^{\,a_3^{\,\cdots}} \bmod \phi(x)$ and then compute $a_1^r \mod x$ directly.

    In the prime decomposition of $y$ every prime $p|a_1$. So for sufficiently large $k$, $a_1^k \equiv 0 \mod y$. So as $k = a_2^{\; a_3^{\;\cdots}}$ becomes arbitrarily large, $a_1^{\,a_2^{\,\cdots}} \equiv 0\mod y$.

As the recursive calls have strictly decreasing $m$ due to repeated application of the totient function $\phi$, this algorithm terminates for any $a$ and any $m$.

Now, we can define a function on a sequence $a$, $\text{MPT(a)}$ (for modular prime tower). It returns the infinite sequence $a_1^{\,a_2^{\,\cdots}} \bmod 1, \quad a_1^{\,a_2^{\,\cdots}} \bmod 2, \quad a_1^{\,a_2^{\,\cdots}} \bmod 3, \quad \ldots$.

Is $\text{MPT}(a)$ injective for any $a$ where all $a_i > 1$? That is, is the output of $\text{MPT}$ unique for all inputs?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.