6
$\begingroup$

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?

$\endgroup$

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.