Evaluate modular power towers
Pyth, 23 bytes

M&amp;tG.^HsgBu-G/GH{PGGhHG


Defines a function g, taking m and n in that order.

Try it online

How it works

M&amp;tG.^HsgBu-G/GH{PGGhHG
M                         def g(G, H):
 &amp;tG                        0 if G == 1, else …
                 PG         prime factors of G
                {           deduplicate that
          u-G/GH   G        reduce that on lambda G,H:G-G/H, starting at G
                              (this gives the Euler totient φ(G))
        gB          hH      bifurcate: two-element list [that, g(that, H + 1)]
       s                    sum
    .^H               G     H^that mod G


Python 2, 109 76 bytes



import sympy
def g(n,m):j=sympy.totient(m);return m-1and pow(n,j+g(n+1,j),m)


Try it online!

Why it works

We use the following generalization of Euler’s theorem.

Lemma. n2φ(m) ≡ nφ(m) (mod m) for all n (whether or not n is coprime to m).

Proof: For all prime powers pk dividing m,


If p divides n, then because φ(m) ≥ φ(pk) = pk − 1(p − 1) ≥ 2k − 1 ≥ k, we have n2φ(m) ≡ 0 ≡ nφ(m) (mod pk).
Otherwise, because φ(pk) divides φ(m), Euler’s theorem gives n2φ(m) ≡ 1 ≡ nφ(m) (mod pk).


Therefore, n2φ(m) ≡ nφ(m) (mod m).

Corollary. If k ≥ φ(m), then nk ≡ nφ(m) + (k mod φ(m)) (mod m).

Proof: If k ≥ 2φ(m), the lemma gives nk = n2φ(m)nk - 2φ(m) ≡ nφ(m)nk - 2φ(m) = nk - φ(m) (mod m) and we repeat until the exponent is less than 2φ(m).