Introduction

An exponential tower (also called a power tower or tetration) is an expression like a^(b^(c^d)), evaluated from the top down (right to left). Computing such towers modulo a prime is a classic number theory problem that appears in competitive programming and cryptography. Naive computation is impossible because the intermediate values grow astronomically, but Euler's theorem provides an efficient recursive approach.

Key Concepts

Euler's Theorem

For any integer a and prime p where gcd(a, p) = 1:

a^(p-1) ≡ 1 (mod p)

This means the exponent can be reduced modulo p-1 (which is Euler's totient for a prime). More generally, for any modulus m:

a^e ≡ a^(e mod φ(m)) (mod m)

where φ(m) is Euler's totient function.

Euler's Totient for a Prime

For a prime p:

φ(p) = p - 1

For a prime power:

φ(p^k) = p^k - p^(k-1)

The Algorithm

To evaluate a tower a₁^(a₂^(a₃^(...^aₙ))) mod m:

1. If the tower has one element, return a₁ mod m
2. Compute the exponent: recursively evaluate the rest of the tower mod φ(m)
3. Return a₁^(exponent) mod m using modular exponentiation

The recursion terminates because applying Euler's totient repeatedly eventually reaches 1.

Pseudocode

1def tower_mod(bases, m):
2    """Evaluate bases[0]^(bases[1]^(bases[2]^...)) mod m."""
3    if m == 1:
4        return 0  # anything mod 1 = 0
5    if len(bases) == 1:
6        return bases[0] % m
7
8    # Compute exponent mod φ(m)
9    phi_m = euler_totient(m)
10    exponent = tower_mod(bases[1:], phi_m)
11
12    return pow(bases[0], exponent, m)

Worked Example

Evaluate 3^(4^5) mod 7:

Step 1: We need 3^(4^5) mod 7. Since 7 is prime, φ(7) = 6.

Step 2: Reduce the exponent: compute 4^5 mod 6.

• 4^5 = 1024
• 1024 mod 6 = 4

Step 3: Compute 3^4 mod 7.

• 3^4 = 81
• 81 mod 7 = 4

Result: 3^(4^5) ≡ 4 (mod 7)

Python Implementation

1from math import gcd
2
3def euler_totient(n):
4    """Compute Euler's totient function φ(n)."""
5    result = n
6    p = 2
7    temp = n
8    while p * p <= temp:
9        if temp % p == 0:
10            while temp % p == 0:
11                temp //= p
12            result -= result // p
13        p += 1
14    if temp > 1:
15        result -= result // temp
16    return result
17
18def mod_tower(bases, m):
19    """Evaluate the power tower bases[0]^(bases[1]^(...)) mod m."""
20    if m == 1:
21        return 0
22    if not bases:
23        return 1  # empty tower = 1 (identity for exponentiation)
24    if len(bases) == 1:
25        return bases[0] % m
26
27    phi_m = euler_totient(m)
28    exponent = mod_tower(bases[1:], phi_m)
29
30    # Handle the case where base and modulus share factors
31    return pow(bases[0], exponent, m)
32
33# Examples
34print(mod_tower([3, 4, 5], 7))     # 3^(4^5) mod 7 = 4
35print(mod_tower([2, 3, 4], 1000))  # 2^(3^4) mod 1000 = 2^81 mod 1000
36print(mod_tower([7, 7, 7, 7], 13)) # 7^(7^(7^7)) mod 13

C++ Implementation

1#include <cstdint>
2
3uint64_t euler_totient(uint64_t n) {
4    uint64_t result = n;
5    for (uint64_t p = 2; p * p <= n; ++p) {
6        if (n % p == 0) {
7            while (n % p == 0) n /= p;
8            result -= result / p;
9        }
10    }
11    if (n > 1) result -= result / n;
12    return result;
13}
14
15uint64_t power_mod(uint64_t base, uint64_t exp, uint64_t mod) {
16    uint64_t result = 1;
17    base %= mod;
18    while (exp > 0) {
19        if (exp & 1) result = (__uint128_t)result * base % mod;
20        exp >>= 1;
21        base = (__uint128_t)base * base % mod;
22    }
23    return result;
24}
25
26uint64_t tower_mod(uint64_t* bases, int n, uint64_t m) {
27    if (m == 1) return 0;
28    if (n == 1) return bases[0] % m;
29    uint64_t phi = euler_totient(m);
30    uint64_t exp = tower_mod(bases + 1, n - 1, phi);
31    return power_mod(bases[0], exp, m);
32}

Edge Cases

• Base is 0: 0^(anything > 0) = 0, but 0^0 = 1 by convention.
• Modulus is 1: Any number mod 1 is 0.
• Base and modulus share factors: When gcd(a, m) > 1, Euler's theorem does not directly apply. For the general case, use the lifting-the-exponent lemma or handle small exponents explicitly.
• Very deep towers: The recursion depth equals the tower height. Since φ applied repeatedly reaches 1 quickly (in O(log m) steps), the recursion terminates even for very tall towers.

Common Pitfalls

• Evaluating left to right: Power towers are always evaluated right to left (top down). 2^3^4 means 2^(3^4) = 2^81, not (2^3)^4 = 8^4 = 4096.
• Forgetting the totient reduction: Without reducing the exponent mod φ(m) at each level, intermediate values overflow any integer type.
• Not handling gcd(base, mod) > 1: The simple Euler approach assumes coprimality. For competitive programming, check if additional handling is needed.

Summary

• Use Euler's theorem to reduce exponents: a^e mod m = a^(e mod φ(m)) mod m
• Apply recursively: compute each level's exponent mod the totient of the current modulus
• The recursion terminates quickly because repeated totient application reaches 1 in O(log m) steps
• Works efficiently even for towers with billions of levels