INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A23

ITERATED EXPONENTS IN NUMBER THEORY

Daniel B. Shapiro

Department of Mathematics, Ohio State University, Columbus, OH 43210

                        shapiro@math.ohio-state.edu

S. David Shapiro

1616 Lexington Ave #D, El Cerrito, CA 94530

                            gavelmaven@aol.com

Received: 8/21/06, Revised: 2/17/07, Accepted: 4/14/07, Published: 5/8/07

Abstract

We show that if a_{1}, a_{2}, a_{3}, … is a sequence of positive integers and k is given, then the sequence a_{1}, a_{1}^{a_{2}}, a_{1}^{a_{2}^{a_{3}}}, … becomes constant when reduced (mod k). We also consider the sequence 1^{1}, 2^{2}, 3^{3}, … (mod k), showing that this sequence, and related ones like n^{n^{n}} (mod k), are eventually periodic.

–Dedicated to the memory of Prof. Arnold Ross

1. Introduction

What is the units digit of a number like 7^{8^{9^{10}}}? Problems of this nature often appear on contests, and we consider various generalizations in this article. For instance we show that if a_{1}, a_{2}, a_{3}, … is a sequence of positive integers and k is given, then the sequence a_{1}, a_{1}^{a_{2}}, a_{1}^{a_{2}^{a_{3}}}, … becomes constant when reduced (mod k). We also consider the sequence 1^{1}, 2^{2}, 3^{3}, … (mod k), showing that this sequence, and related ones like n^{n^{n}} (mod k), are eventually periodic. With further work we are able determine their minimal periods. Using those ideas we prove that if u is relatively prime to k then the congruences x^{x} ≡ u (mod k) and y^{y^{y}} ≡ u (mod k) have solutions. Finally, we lift these ideas to the ring of p-adic integers and pose some open questions.

The methods used here are part of elementary number theory and we have attempted to present the ideas in as elementary a way as possible. The results proved here were originally obtained in 1985, but not published previously.

Many papers have been written about limits of the form x^{x^{x^{·^{·^{·}}}}}, where x is a real or complex number. In fact, such convergence questions go back to Bernoulli, Goldbach and Euler. Results and references to the literature appear in Anderson (2004), Knoebel (1981), and Baker and Rippon (1985). However, relatively little work has been done on the arithmetic aspects of such numbers when x is an integer. Early work in this direction was done by Maurer (1901) and Cunningham (1907). Fifty years later some related papers appeared in Polish journals by Sierpiński (1950), Hampel (1955) and Schinzel-Sierpiński (1959). More recently Blakley-Borosh (1983) and Dawson (1994) published further results about the periodic behavior of these sequences modulo k. In this article we unify and extend these arithmetic results. In the first sections below we have repeated some of the results of Blakley-Borosh and Dawson in order to have a self-contained presentation and to clarify the notations.

2. Reducing Iterated Exponents Modulo k

The symbol ℤ stands for the set of integers and ℤ^{+} is the subset of positive integers. We assume the reader is familiar with some elementary number theory.

Definition 2.1. If a, b are positive integers, define a ↑ b = a^{b}. These arrows are always associated to the right if no parentheses are present: a ↑ b ↑ c = a ↑ (b↑c). The related “E” notation is defined in analogy with “Σ” for sums:

E_{j=1}^{s} a_{j} = a_{1} ↑a_{2} ↑…↑a_{s} = a_{1}^{a_{2}^{.^{.^{.^{as}}}}} .

Recursively we can define: E_{j=1}^{s} a_{j} = a_{1} ↑(E_{j=2}^{s} a_{j}) , if s > 1.

The goal of this section is to investigate conditions on integer sequences {a_{j}} and {b_{j}} which imply that a_{1} ↑ a_{2} ↑ … ↑ a_{s} ≡ b_{1} ↑ b_{2} ↑ … ↑ b_{s} (mod k). To begin let’s refine the usual definition of the order of an element (mod k) by allowing non-units.

Definition 2.2. Given n and k, the sequence 1, n, n^{2}, n^{3}, … (mod k) is eventually periodic. The order, o_{k}(n) = o(n mod k), is the length of that periodic cycle. The tail length ρ_{k}(n) is the number of terms in the sequence before the repeating cycle begins. (The notations ρ and o are suggested by the shapes of those letters.)

For example the powers of 2 (mod 40) are 1, 2, 4, 8, 16, 32, 24, 8, 16, 32, …. The terms (1, 2, 4) form an initial “tail” so that ρ_{40}(2) = 3. The repeating portion or “cycle” is (8, 16, 32, 24), so that o_{40}(2) = 4.

Lemma 2.3. Given positive integers n and k:

(a) ρ_{k}(n) and o_{k}(n) depend only on n modulo k.

(b) If r ≠ s, then n^{r} ≡ n^{s} (mod k) ⟺ r ≡ s (mod o_{k}(n)) and r, s ≥ ρ_{k}(n).

Proof. These statements follow from the definition. For instance, for (b), any repetition in the sequence {n^{r} (mod k)} must occur within the repeating cycle.

When n is invertible (mod k), the sequence 1, n, n^{2}, n^{3}, … (mod k) is purely periodic. Then the cycle length is the first exponent which yields 1. That is, ρ_{k}(n) = 0 and o_{k}(n) = min{d : d > 0 and n^{d} ≡ 1 (mod k)}.

Lemma 2.4. Given k, n ∈ ℤ^{+}, factor k = k′(n)k′′(n), where k′(n) and n are coprime, and every prime factor of k′′(n) also divides n.

(1) o_{k}(n) = o_{k′(n)}(n).

(2) ρ_{k}(n) = min{r ∈ ℤ : r ≥ 0 and k′′(n)|n^{r}}.

Proof. The values n^{r} (mod k′) are purely periodic while n^{r} ≡ 0 (mod k′′) for all large r. This yields the expression for ρ_{k}(n). To check the length of the eventual cycle, note: n^{t} ≡ n^{t+w} for both moduli k′ and k′′ if and only if n^{t} ≡ n^{t+w} mod k.

Suppose n = p_{1}^{r_{1}}p_{2}^{r_{2}} ⋯ p_{t}^{r_{t}}, where the p_{i} are distinct primes and every r_{i} > 0. Arrange the prime factors of k so that k = p_{1}^{m_{1}}p_{2}^{m_{2}} ⋯ p_{t}^{m_{t}} ⋯ p_{u}^{m_{u}}, where m_{i} ≥ 0. Then k′′(n) =

p_{1}^{m_{1}}p_{2}^{m_{2}} ⋯ p_{t}^{m_{t}} and ρ_{k}(n) = max_{1≤i≤t}\{⌈\frac{m_{i}}{r_{i}} ⌉\}.

(Here, ⌈x⌉ is the smallest integer ≥ x.)

Euler proved that c^{φ(k)} ≡ 1 (mod k) for every c coprime to k. Here the Euler function φ(k) is the number of elements in the group of units 𝕌_{k} = (ℤ/kℤ)^{∗}. Equivalently, φ(k) is the number of integers c coprime to k with 0 ≤ c < k. For our purposes, the smallest exponent for 𝕌_{k} is a more important value.

Definition 2.5. For k ∈ ℤ^{+} define λ(k) to be the smallest positive integer e such that n^{e} ≡ 1 (mod k) for every n coprime to k. Define R(k) = max{ρ_{k}(n) : 0 ≤ n < k}.

This λ(k) is the “exponent” of the abelian group 𝕌_{k}. Carmichael (1910) showed how to compute λ(k) from the prime factorization of k.

Proposition 2.6. Suppose k = p_{1}^{m_{1}}p_{2}^{m_{2}} … p_{t}^{m_{t}} in prime factorization.

(0) R(k) = max{m_{i}}.

(1) λ(k) is the maximal order of an element in 𝕌_{k}. If d|k then λ(d)|λ(k).

(2) If a, b are coprime, then λ(ab) = lcm{λ(a), λ(b)}; In general, λ(lcm{a, b}) divides lcm{λ(a), λ(b)}.

(3) If p is an odd prime, λ(p^{m}) = p^{m−1}(p − 1).

(4) λ(2) = 1, λ(4) = 2, and λ(2^{m}) = 2^{m−2} whenever m ≥ 3.

Proof. These results follow from the ideas used to determine which of the groups 𝕌_{n} are cyclic. Key steps in an elementary proof are:

(i) If x, y ∈ 𝕌_{m}, there exists z ∈ 𝕌_{m} with o_{k}(z) = lcm{o_{k}(x), o_{k}(y)}.

(ii) If p is an odd prime, there is an element of order p^{m−1} in 𝕌_{p^{m}}.

(iii) There is an element of order 2^{m−2} in 𝕌_{2^{m}} whenever m ≥ 3. Further information appears in many references, like [Carmichael: 1910], [Vinogradov: 1954] pp. 106-107, or [H. Shapiro: 1983] Theorems 6.2.2 and 6.3.1.

For part (2), when a, b are coprime apply the Chinese Remainder Theorem. For the general case, factor lcm{a, b} = a′b′ where a′ | a, b′ | b and a′, b′ are coprime. Then λ(lcm{a, b}) = λ(a′b′) = lcm{λ(a′), λ(b′)} divides lcm{λ(a), λ(b)}.

As a corollary we see that λ(k) and R(k) are the o and ρ for everything in ℤ/kℤ, taken simultaneously.

Corollary 2.7. Let k be a positive integer.

(1) For every n ∈ ℤ, o_{k}(n)|λ(k) and ρ_{k}(n) ≤ R(k).

(2) Let a, b be nonnegative integers. Then

n^{a} ≡ n^{b} (mod k) for every n ⟺ \{ \begin{matrix}either a = b, \\ or a ≡ b (mod λ(k)) and a, b ≥ R(k). \end{matrix}

Proof. (1) o_{k}(n) = o_{k′}(n) which divides λ(k′). Since k′ |k we apply (2.6)(2) above. (2) Apply Lemma 2.3.

Consequently, the mod k reduction of, say, a_{1}^{a_{2}^{a_{3}}} = a_{1} ↑ a_{2} ↑ a_{3} should depend only on the residues of a_{1} (mod k), of a_{2} (mod λ(k)) and of a_{3} (mod λ(λ(k))). For example, since λ(λ(8)) = 1, this ought to imply that the value of a_{1} ↑ a_{2} ↑ x (mod 8) is independent of the choice of x. However 2^{2^{1}} ≢ 2^{2^{2}} (mod 8). This happens because the value 2^{2^{1}} = 4 lies in the “tail” rather than the “cycle”. The next few results detail the inequalities needed to avoid this problem. To simplify notations, define λ^{r} recursively by setting λ^{0}(k) = k and λ^{r} = λ ∘ λ^{r−1} for r > 0.

Lemma 2.8. Suppose a_{r} ≡ b_{r} (mod λ^{r−1}(k)) for r = 1, …, s. Then E_{i=1}^{s} a_{i} ≡ E_{i=1}^{s} b_{i} (mod k),

provided E_{i=r+1}^{s}a_{i} and E_{i=r+1}^{s}b_{i} are ≥ R(λ^{r−1}(k)) whenever 1 ≤ r < s.

Proof. Induction on s using Corollary 2.7.

Proposition 2.9. Suppose a_{r} ≡ b_{r} (mod λ^{r−1}(k)) for r = 1, …, s. Suppose further that

a_{r}, b_{r} ≥ 2 for 1 < r ≤ s; and a_{s}, b_{s} ≥ R(λ^{s−2}(k)). Then E_{i=1}^{s} a_{i} ≡ E_{i=1}^{s} b_{i} (mod k).

Proof. It suffices to verify the inequalities in (2.8). The case r = s−1 is assumed. The other inequalities follow by repetition of the following claim. Claim: If a ≥ 2 and a ≥ R(λ(k)) then 2^{a} ≥ R(k). This is clear when R(k) ≤ 4 since 2^{a} ≥ 2^{2} = 4. If R(k) > 4 the definitions imply that R(λ(k)) ≥ R(k) − 2. Since 2^{x−2} ≥ x whenever x ≥ 4 we find that 2^{a} ≥ 2^{R(k)−2} ≥ R(k).

Definition 2.10. For k ∈ ℤ^{+} the height of k is h(k) = min{s : λ^{s}(k) = 1}.

Checking small cases we find: h(k) = 0 ⟺ k = 1; h(k) = 1 ⟺ k = 2; and h(k) = 2 ⟺ k = 3, 4, 6, 8, 12 or 24.

Corollary 2.11. If a_{j} ∈ ℤ^{+}, then the towers a_{1} ↑a_{2} ↑⋯↑a_{h(k)} ↑c reduce to the same value in ℤ/kℤ, for every c > 1. Consequently, a_{1} ↑ a_{2} ↑ ⋯ ↑ a_{s} ↑ x (mod k) is independent of the value of x ∈ ℤ^{+}, provided s > h(k).

Proof. If a_{j} = 1 for some j ≤ h(k), the result is trivial, so assume all a_{j} ≥ 2. Compare two such towers differing only in the top entries a_{h(k)+1} = c by checking the conditions in (2.9) when s = h(k) + 1. They all hold provided c ≥ 2. The second statement follows using c = a_{h(k)+1} ↑⋯↑a_{s} ↑x.

Thus, for any sequence {a_{j}} ⊆ ℤ^{+} and k ∈ ℤ^{+}, the sequence of “partial powers” E_{i=1}^{s} a_{i} becomes stable (mod k) as s increases; all terms with s > h(k) are congruent (mod k).

3. The Sequences n↑↑t (mod k)

Define the double-arrow n↑↑t to be E_{i=1}^{t}(n), an exponential ladder of t n’s. Then n↑↑0 = 1, n ↑↑ 1 = n, n ↑↑ 2 = n^{n}, etc. This is part of the arrow notation as defined in Knuth (1976).

For a fixed modulus k, Hampel (1955) showed that the sequence 1^{1}, 2^{2}, 3^{3}, … (mod k) is eventually periodic and determined its minimal period. In this section we generalize that result, showing for any t ≥ 0, the sequence 1 ↑↑ t, 2 ↑↑ t, 3 ↑↑ t, … is eventually periodic (mod k), and computing its minimal period, L_{t}(k).

For fixed k and n, the sequence n, n^{n}, n^{n^{n}}, n↑↑4, … eventually becomes constant (mod k). In fact, Corollary 2.11 implies that n ↑↑ t ≡ n ↑↑ (t + 1) (mod k) whenever t > h(k). The “stable value” \overline{α}_{k}(n) of this sequence n↑↑t (mod k) is a well defined element of ℤ/kℤ. However, it is best to define a positive integer representing this value, since we will also use it as an exponent.

Definition 3.1. For k, n ∈ ℤ^{+} let α_{k}(n) = n ↑↑ (1 + h(k)). This is defined recursively by: α_{1}(n) = n and α_{k}(n) = n↑α_{λ(k)}(n) for every k ≥ 2.

Then α_{k}(n) ≡ n↑↑t (mod k) for every t > h(k), and we may consider this value in ℤ/kℤ as the “infinite tower” of exponents:

α_{k}(n) ≡ n^{n^{n^{·^{·^{·}}}}} (mod k).

Corollary 3.2. If k, n ∈ ℤ^{+} then x = α_{k}(n) satisfies x ≡ n^{x} (mod k).

Proof. With t = 1 + h(k), Corollary 2.11 implies x = n↑↑t ≡ n↑↑(t + 1) ≡ n↑(n↑↑t) = n^{x} (mod k).

Let’s examine a few numerical cases. Table 1 lists the sequences α_{k}(n) reduced to their least nonnegative residues modulo k, for the first few values of k and n.

\begin{matrix}k \^{n} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ 2 & (1 & 0) & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 3 & (1 & 1 & 0 & 1 & 2 & 0) & 1 & 1 & 0 & 1 & 2 & 0 & 1 & 1 & 0 & 1 & 2 & 0 & 1 & 1 & 0 & 1 & 2 \\ 4 & (1 & 0 & 3 & 0) & 1 & 0 & 3 & 0 & 1 & 0 & 3 & 0 & 1 & 0 & 3 & 0 & 1 & 0 & 3 & 0 & 1 & 0 & 3 \\ 5 & (1 & 1 & 2 & 1 & 0 & 1 & 3 & 1 & 4 & 0 & 1 & 1 & 3 & 1 & 0 & 1 & 2 & 1 & 4 & 0) & 1 & 1 & 2 \\ 6 & (1 & 4 & 3 & 4 & 5 & 0) & 1 & 4 & 3 & 4 & 5 & 0 & 1 & 4 & 3 & 4 & 5 & 0 & 1 & 4 & 3 & 4 & 5 \\ 7 & (1 & 2 & 6 & 4 & 3 & 1 & 0 & 1 & 1 & 4 & 2 & 1 & 6 & 0 & 1 & 2 & 5 & 1 & 5 & 1 & 0 & 1 & 4 \\ 8 & (1 & 0 & 3 & 0 & 5 & 0 & 7 & 0) & 1 & 0 & 3 & 0 & 5 & 0 & 7 & 0 & 1 & 0 & 3 & 0 & 5 & 0 & 7 \\ 9 & (1 & 7 & 0 & 4 & 2 & 0 & 7 & 1 & 0 & 1 & 5 & 0 & 4 & 4 & 0 & 7 & 8 & 0) & 1 & 7 & 0 & 4 & 2 \end{matrix}

Table 1: The (k, n)-entry is α_{k}(n) (mod k).

Here k indexes the rows and n indexes the columns. Parentheses indicate the first repeating block of each sequence.

As one example let’s calculate the residue of α_{7}(5) (mod 7). First check that h(7) = 3 (since λ(7) = 6, λ^{2}(7) = 2 and λ^{3}(7) = 1). By definition, α_{7}(5) = 5↑↑4 = 5^{5^{5^{5}}}, a number of more than 2 · 10^{17} digits. To reduce it modulo 7 we first compute that 5 ↑↑ 3 ≡ 5^{5^{5}} ≡ (−1)^{5^{5}} ≡ −1 ≡ 5 (mod 6). Conclude from (2.7) that α_{7}(5) ≡ 5^{5} ≡ 3 (mod 7). Further values for k = 7 appear in Table 2 below. These calculations suggest that the sequence α_{k}(n) (mod k) is always periodic (with no tail). The minimal periods L(k) are: L(1) = 1, L(2) = 2, L(3) = 6, L(4) = 4, L(5) = 20, L(6) = 6, L(7) = 42, L(8) = 8, L(9) = 18. Our goal is to find a simple formula for these periods.

Proposition 2.9 shows that the sequences {n ↑↑ t (mod k)} are eventually periodic and provides natural candidates for their periods.

Lemma 3.3. Suppose k, t > 0 are given and let L = lcm{k, λ(k), λ^{2}(k), …, λ^{t−1}(k)}, the least common multiple. If t ≥ 2 and integers a, b satisfy a, b ≥ R(λ^{t−2}(k)), then a ≡ b (mod L) implies a↑↑t ≡ b↑↑t (mod k).

Proof. If a ≡ 1 or b ≡ 1 (mod k) the conclusion is trivial, so we may assume a, b ≥ 2. By hypothesis, a ≡ b (mod λ^{r−1}(k)) for r = 1, 2, ..., t. The implication now follows from Proposition 2.9.

Definition 3.4. For k, t ∈ ℤ^{+}, let L_{t}(k) be the minimal period of the eventually periodic sequence {n↑↑t (mod k)}. Let L(k) be the minimal period of the periodic sequence {α_{k}(n) (mod k)}.

Observe that (2.11) implies L_{t}(k) = L(k) whenever t ≥ h(k). Also L_{1}(k) = k for all k. Moreover, by (3.3), L_{t}(k) divides lcm{k, λ(k), λ^{2}(k), …, λ^{t−1}(k)}, since any period is a multiple of the minimal period.

Theorem 3.5. L_{t}(k) = lcm{k, λ(k), λ^{2}(k), …, λ^{t−1}(k)}.

The proof of this theorem is preceded by several lemmas. Our strategy is to compute L_{t}(k) when k is a prime power, then to glue these formulas together using the next lemma.

Lemma 3.6. (i) If d | k then L_{t}(d) | L_{t}(k); (ii) L_{t}(lcm{k_{1}, k_{2}}) = lcm{L_{t}(k_{1}), L_{t}(k_{2})}; (iii) λ^{s}(lcm{a, b}) divides lcm{λ^{s}(a), λ^{s}(b)}.

Proof. (i) If a ≡ b (mod L_{t}(k)) and a, b are large then a↑↑t ≡ b↑↑t (mod k). Then if d|k, the sequence {n↑↑t (mod d)} has L_{t}(k) as a period. Hence the minimal period L_{t}(d) divides L_{t}(k).

(ii) Let l = lcm{k_{1}, k_{2}} and m = lcm{L_{t}(k_{1}), L_{t}(k_{2})}. Part (i) implies that m | L_{t}(l). Conversely suppose a ≡ b (mod m) and a, b are large. Then a ≡ b (mod L_{t}(k_{j})), implying a ↑↑ t ≡ b ↑↑ t (mod k_{j}) for j = 1, 2. Then the congruence holds (mod l), and the minimal period L_{t}(l) divides m.

(iii) This property of λ follows by repeated application of (2.6)(2).

Lemma 3.7. If p is prime then p^{m} |L_{t}(p^{m}).

Proof. We may assume t ≥ 2. It is easy to check that p | L_{t}(p), since n ↑↑ t ≡ 0 (mod p) iff n ≡ 0 (mod p). Suppose m > 1. By induction p^{m−1} | L_{t}(p^{m−1}) so it also divides L_{t}(p^{m}). Then L_{t}(p^{m}) = p^{m−1}y for some y, and we want to prove p | y. By definition of L_{t} we have (n + p^{m−1}y) ↑↑ t ≡ n ↑↑ t (mod p^{m}) whenever n ≥ R(λ^{t−2}(p^{m})). We use n = 1 + p^{m}, which does satisfy that inequality. Setting r = (1 + p^{m} + p^{m−1}y)↑↑(t − 1), the congruence becomes:

(1 + p^{m−1}y)^{r} ≡ (1 + p^{m} + p^{m−1}y)↑↑t ≡ (1 + p^{m})↑↑t ≡ 1 (mod p^{m}). The binomial theorem then implies 1 + rp^{m−1}y ≡ 1 (mod p^{m}), so that ry ≡ 0 (mod p). Since r ≡ 1 (mod p), we get p|y as claimed.

Lemma 3.8. If p is prime and t ≥ 2 then L_{t−1}(p − 1)|L_{t}(p).

Proof. For ℓ = L_{t}(p), we have (n + ℓ)↑↑t ≡ n↑↑t (mod p), for every large n. Since p|ℓ we find: n↑((n + ℓ)↑↑(t − 1)) ≡ (n + ℓ)↑↑t ≡ n↑↑t ≡ n↑(n↑↑(t − 1)) (mod p), provided n ≥ R(λ^{t−2}(p)). Suppose g is a generator of the group 𝕌_{p}. Then for any large n with n ≡ g (mod p), the previous congruence implies:

(n + ℓ)↑↑(t − 1) ≡ n↑↑(t − 1) (mod p − 1). (*)

Consequently, (*) holds for any large n of the form n = g+px+wy, where w = L_{t−1}(p−1). Note that w and p are coprime, since w divides lcm{p−1, λ(p−1), … }. Therefore, congruence (*) holds for all large integers n, so that the minimal period w must divide ℓ.

Lemma 3.9. If p is prime, and t ≥ 2, then

lcm{p^{m}, λ(p^{m}), …, λ^{t−1}(p^{m})} = lcm{p^{m}, p − 1, λ(p − 1), …, λ^{t−2}(p − 1)}.

Proof. If p = 2 both sides equal 2^{m}. Suppose p is odd. Since (p − 1)|λ(p^{m}), (2.6)(1) implies λ^{r−1}(p − 1) | λ^{r}(p^{m}), and the right side divides the left. To prove: λ^{r}(p^{m}) divides the right side, whenever 0 ≤ r < t. This is easy for r = 0, 1, so assume r > 1 and use induction. Since λ^{r}(p^{m}) = λ^{r−1}(p^{m−1}(p−1)) divides lcm{λ^{r−1}(p^{m−1}), λ^{r−1}(p−1)}, by (3.6)(iii), we may apply the induction hypothesis to complete the proof.

Proof of Theorem 3.5. We prove this statement by induction on k. The formula for k = 1 is trivial, so we assume k > 1 and that the formula for L_{t}(a) holds true for every a < k.

First suppose k = p^{m} is a prime power. We want to prove that L_{t}(p^{m}) equals the quantity in Lemma 3.9, which we call M here. As mentioned after (3.4), L_{t}(p^{m}) divides M. By induction, L_{t−1}(p − 1) = lcm{p − 1, λ(p − 1), …, λ^{t−2}(p − 1)}, so that M = lcm{p^{m}, L_{t−1}(p − 1)}. The fact that M divides L_{t}(p^{m}) now follows from (3.7), (3.8) and (3.6)(i). Hence L_{t}(p^{m}) = M.

Proceeding by induction for arbitrary k, we may assume that k > 1 is not a prime power. Then there is a factorization k = ab where a, b are coprime and a, b < k. As noted before, L_{t}(k) divides the quantity u = lcm{k, λ(k), …, λ^{t−1}(k)}. Since k = ab, (3.6)(iii) implies that u divides lcm{a, b, λ(a), λ(b), …, λ^{t−1}(a), λ^{t−1}(b)}. The induction hypothesis implies that this last quantity equals lcm{L_{t}(a), L_{t}(b)}, which equals L_{t}(ab) = L_{t}(k) by (3.6)(ii), since a, b are coprime. Then all the terms in this divisor chain are equal and the Theorem follows.

Corollary 3.10. (1) If p is prime then L_{t}(p^{m}) = lcm{p^{m}, L_{t−1}(p − 1)}; (2) L_{t}(k) = lcm{k, L_{t−1}(λ(k))} = lcm_{p|k}{k, L_{t−1}(p − 1)}.

Proof. By this notation we mean that if k = p_{1}^{m_{1}}p_{2}^{m_{2}} … p_{s}^{m_{s}} is the prime factorization of k then L_{t}(k) = lcm{k, L_{t−1}(p_{1} − 1), …, L_{t−1}(p_{s} − 1)}. These formulas follow from (3.9) and Theorem 3.5.

Corollary 3.11. The period L(k) of the sequence \overline{α}_{k}(0), \overline{α}_{k}(1), \overline{α}_{k}(2), , … in ℤ/kℤ has the following properties:

(1) L(k) = lcm{k, λ(k), λ^{2}(k), … } = lcm_{p|k}{k, L(p − 1)};

(2) If d | k then L(d) | L(k). Moreover, L(lcm{a, b}) = lcm{L(a), L(b)} and L(mn) = lcm{mn, L(m), L(n)}.

(3) The periods k = L_{1}(k), L_{2}(k), …, L(k) form a divisor chain (each term divides the next).

(4) L(λ(k)) divides L(k).

(5) L(L(k)) = L(k).

(6) L(k) = k ⟺ λ(k)|k ⟺ for prime p, p|k implies (p − 1)|k.

Proof. (1) Use Theorems 3.5 and 3.10, noting that L(k) = L_{t}(k) whenever t ≥ h(k). The other parts follow from (1). For instance, for (6) note that (1) implies: L(k) = k if and only if every λ^{r}(k) | k. By (2.6)(1), that is equivalent to: λ(k) | k. The formula for λ(k) in (2.6) implies that this occurs exactly when (p − 1)|k for every prime factor p of k.

The sequence α_{k}(n) (mod k) was viewed as a mapping \overline{α}_{k} : ℤ^{+} → ℤ/kℤ. Knowing the periodicity we re-interpret it (with some abuse of notation) as a map \overline{α}_{k} : ℤ/L(k)ℤ → ℤ/kℤ. This observation explains how to make sense of \overline{α}_{k}(n) for negative values of n.

Proposition 3.12. (i) \overline{α}_{k}(0) = 0 and \overline{α}_{k}(−1) = −1. (ii) If n is even then \overline{α}_{k}(−n) = \overline{α}_{k}(n). (iii) If n ∈ 𝕌_{L(k)} is a unit, then \overline{α}_{k}(−n) = −\overline{α}_{k}(n^{−1}).

Proof. Assume k > 1 so that L = L(k) is even. (i) Note that \overline{α}_{k}(−1) = \overline{α}_{k}(L − 1) = (−1)^{s} in ℤ/kℤ, where s = a_{λ(k)}(L − 1) is odd.

(ii) Induct on k. By the periodicity we may assume 0 ≤ n < L. Then \overline{α}_{k}(−n) ≡ α_{k}(L − n) ≡ (L − n)^{s} ≡ (−n)^{s} (mod k), where s = α_{λ(k)}(L − n). Since n and L are even, s is even and \overline{α}_{k}(−n) ≡ n^{s} (mod k). Since L is a multiple of L(λ(k)), we have s ≡ \overline{α}_{λ(k)}(−n) (mod λ(k)). Applying the induction hypothesis we find s ≡ α_{λ(k)}(n) (mod λ(k)) and therefore \overline{α}_{k}(−n) ≡ \overline{α}_{k}(n) (mod k), as claimed.

(iii) Using a similar strategy (but with less detail), we have \overline{α}_{k}(n^{−1}) ≡ n^{−1} ↑s ≡ n↑(−s) (mod k), where s ≡ \overline{α}_{λ(k)}(n^{−1}) (mod λ(k)). By induction s ≡ −\overline{α}_{λ(k)}(−n) (mod λ(k)). Then since n is odd, \overline{α}_{k}(n^{−1}) ≡ n↑\overline{α}_{λ(k)}(−n) ≡ −\overline{α}_{k}(−n) (mod k).

It is interesting to look for patterns in tables of values of \overline{α}_{k}(n). For example, here are the values of \overline{α}_{7}(n) arranged in rows of seven. The period is L(7) = 42.

0 1 2 6 4 3 1
0 1 1 4 2 1 6
0 1 2 5 1 5 1
0 1 4 1 4 2 6
0 1 1 3 4 6 1
0 1 2 4 1 2 6
Table 2: \overline{α}_{7}(n) for n = 0, 1, …, 41.

A number of patterns of ±1’s can be observed from such charts. The simplest ones are easily explained.

Proposition 3.13. Let p be an odd prime, and suppose n ≢ 0 (mod p).

(i) If n ≡ 1 (mod p) then α_{p}(n) ≡ 1 (mod p); if n ≡ −1 (mod p) then α_{p}(n) ≡ (−1)^{n} (mod p).

(ii) If p ∤ n and each prime factor of p − 1 divides n, then α_{p}(n) ≡ 1 (mod p).

Proof. α_{p}(n) = n^{s} where s = α_{p−1}(n) ≡ n^{t} (mod p − 1), for some large t. (i) Easy. (ii) Since t is large, (p − 1)|n^{t} = s and the claim follows.

This frequent occurrence of ±1’s doesn’t happen for every value of k. In the next section we will prove that when L(k) = k, the value 1 occurs only once in each period of α_{k}(n) (mod k). For example, since L(7) = 42 we know from Corollary 3.11(5) that L(42) = 42. Here is a table of the values of \overline{α}_{42}(n), arranged in rows of seven. Note that these values induce those of \overline{α}_{7}(n) after reduction (mod 7).

0 1 16 27 4 17 36
7 22 15 4 23 36 13
28 15 16 5 36 19 22
21 22 11 36 25 16 27
28 29 36 31 4 27 22
35 36 37 4 15 16 41
Table 3: \overline{α}_{42}(n) for n = 0, 1, …, 41.

4. Values Occurring in the Sequences

Which values in ℤ/kℤ are assumed by the sequence \overline{α}_{k}(n) ? That is, for which a ∈ ℤ^{+} does there exist n with α_{k}(n) ≡ a (mod k)? For example, Table 1 shows that the sequence α_{k}(n) assumes all the values in ℤ/kℤ when k = 2, 3, 5, 7. However, when k = 4, 6, 8, 9 some values are missed. An easy argument settles the question when k is a prime, or more generally when k and λ(k) have no prime factors in common.

Lemma 4.1. Suppose k and λ(k) are coprime. For any t ≥ 1 and any a ∈ ℤ, there exists n satisfying n↑↑t ≡ a (mod k).

Proof. If t = 1 the claim is trivial, so assume t ≥ 2. Note that R(k) = 1. By the Chinese Remainder Theorem there exists n ∈ ℤ^{+} such that n ≡ a (mod k) and n ≡ 1 (mod λ(k)). Then n↑↑t = n↑n^{m} where m = n↑↑(t−2). Corollary 2.7 implies: n↑↑t = n↑n^{m} ≡ a↑1 ≡ a (mod k).

Define the map E_{t} : ℤ^{+} → ℤ/kℤ by E_{t}(n) = n ↑↑ t. It is not always surjective, but we will show that every E_{t} is at least surjective on units.

Since E_{t} is eventually periodic with period L = L_{t}(k), we can restrict to values n ≥ R(k) to get an induced map ℤ/Lℤ → ℤ/kℤ. Since L|L(k) we can use the possibly larger domain ℤ/L(k)ℤ for all values of t. Then E_{t} induces a map \overline{E}_{t} : ℤ/L(k)ℤ → ℤ/kℤ, which restricts to a map 𝕌_{L(k)} → 𝕌_{k}. Here is a key observation: When c is an exponent coprime to λ(k) then n^{c} ≡ 1 (mod k) implies n ≡ 1 (mod k). Consequently, if x, y ∈ 𝕌_{k} then x^{c} ≡ y^{c} (mod k) ⟹ x ≡ y (mod k).

Proposition 4.2. Suppose λ(k)|k so that k = L(k). Then for every t, the map \overline{E}_{t} : 𝕌_{k} → 𝕌_{k} is bijective.

Proof. Since 𝕌_{k} is a finite set it suffices to prove \overline{E}_{t} is injective. The case t = 1 is trivial so assume t ≥ 2. The initial cases k = 1, 2 are also easy, so we may assume k > 2 and use induction on k. From λ(k) | k we know λ(λ(k)) | λ(k) and the induction hypothesis implies \overline{E}_{t} : 𝕌_{λ(k)} → 𝕌_{λ(k)} is injective. Suppose x, y ∈ 𝕌_{k} and E_{t}(x) ≡ E_{t}(y) (mod k). Then this congruence holds (mod λ(k)) so that x ≡ y (mod λ(k)), by induction. Since L_{t−1}(λ(k)) = λ(k) by (3.11) we find that E_{t−1}(x) ≡ E_{t−1}(y) (mod λ(k)). Letting c = E_{t−1}(x) we have x^{c} ≡ E_{t}(x) ≡ E_{t}(y) ≡ y^{c} (mod k). From the key observation above we conclude that x ≡ y (mod k).

Corollary 4.3. For any k, the restriction \overline{E}_{t} : 𝕌_{L(k)} → 𝕌_{k} is surjective. In particular, the map \overline{α}_{k} : ℤ^{+} → ℤ/kℤ induces a surjective map \overline{α}_{k} : 𝕌_{L(k)} → 𝕌_{k}.

Proof. Let a ∈ 𝕌_{k}. Since k | L(k) we can choose b ∈ 𝕌_{L(k)} with b ≡ a (mod k). Since L(L(k)) = L(k) by (3.11), Proposition 4.2 provides n ∈ 𝕌_{L(k)} with \overline{E}_{t}(n) ≡ b (mod L(k)). Reducing this congruence shows that \overline{E}_{t}(n) ≡ a (mod k). The final statement follows since α_{k}(n) ≡ E_{t}(n) (mod k) whenever t ≥ h(k).

Here is an alternative approach to the map \overline{α}_{k}. If c = α_{k}(n) then by (3.2), n^{c} ≡ c (mod k). We can solve for n to get n ≡ c^{1/c} (mod k), provided that fractional exponent makes sense. Recall that for c^{s} (mod k), the exponent s behaves modulo λ(k). If s is a unit (mod λ(k)), choose t ∈ ℤ^{+} with t ≡ s^{−1} (mod λ(k)). Then for c ∈ 𝕌_{k}:

x ≡ c^{t} (mod k) is the unique solution to x^{s} ≡ c (mod k). Therefore c^{1/c} (mod k) makes sense whenever c ∈ ℤ^{+} is coprime to both k and λ(k). Since lcm{k, λ(k)} divides L(k), we obtain a well-defined map δ : 𝕌_{L(k)} → 𝕌_{k} given by δ(x) = x^{1/x}. This proves the following result, related to (4.2).

Proposition 4.4. Suppose λ(k) | k so that L(k) = k. The map \overline{α}_{k} : 𝕌_{k} → 𝕌_{k} is bijective with inverse map δ.

Proposition 4.2 can be improved by allowing certain non-units. We will state our best result along these lines.

Theorem 4.5. Define W_{k} = {n ∈ ℤ/kℤ : gcd(n, k, λ(k)) = 1}. Then for every t, the restriction \overline{E}_{t} : W_{L(k)} → W_{k} is surjective.

When λ(k)|k the method used in Proposition 4.4 can extended to W_{k}. However the full theorem does not seem to follow easily from that case. Our proof of the theorem starts with the idea in Lemma 4.1 and uses induction, building up k one prime at a time. It is too long to include here.

We have not found any other useful conditions to ensure that a occurs as a value of \overline{α}_{k}(n). In the other direction there is one easy condition for the number a to be a missing value for the sequences (mod k).

Proposition 4.6. Suppose a, k, and t are given and t ≥ 2, and suppose there exists large x with E_{t}(x) ≡ a (mod k). If p^{d} |k where p^{d} is a prime power, then either p ∤ a or p^{d} |a.

Proof. Suppose p | a. Since E_{t}(x) ≡ a (mod p^{d}) we see that p | x. Since x is large it follows that a ≡ x↑E_{t−1}(x) ≡ 0 (mod p^{d}).

5. p-adic Interpretations.

In this section we assume the reader has some knowledge of the ring ℤ_{p} of p-adic integers. However, to keep the presentation more elementary we include a review of some of the definitions and basic properties. More details appear in various texts like Borevich-Shafarevich (1966) or Koblitz (1977).

Let p be a fixed prime number. If n ≥ m there is a natural reduction map π_{n,m} : ℤ/p^{n}ℤ → ℤ/p^{m}ℤ. The ring ℤ_{p} of p-adic integers is the projective limit \underleftarrow{lim}(ℤ/p^{n}ℤ) relative to these maps π_{n,m}. An element c ∈ ℤ_{p} is defined to be a sequence (c_{1}, c_{2}, c_{3}, …) where c_{n} ∈ ℤ/p^{n}ℤ satisfying the following “coherence” condition: if n ≥ m then π_{n,m}(c_{n}) = c_{m}. With component-wise addition and multiplication, ℤ_{p} becomes an integral domain. The ring of integers ℤ is embedded as a subring of ℤ_{p} by viewing k ∈ ℤ as a constant sequence (k, k, …) in ℤ_{p}. Then u ∈ ℤ_{p} is a p-adic unit (i.e. u is invertible) iff u ≢ 0 (mod p), and every nonzero c ∈ ℤ_{p} factors uniquely as c = p^{m}u for some m ≥ 0 in ℤ and some p-adic unit u ∈ ℤ_{p}^{∗}. Let ord(c) be that exponent m.

Define the p-adic absolute value on ℤ_{p} by setting |0|_{p} = 0 and if c ≠ 0: |c|_{p} = p^{−ord(c)}. This absolute value satisfies the following rules:

|a|_{p} ≤ 1, with equality ⟺ a is a unit in ℤ_{p},
|ab|_{p} = |a|_{p} · |b|_{p}, and
|a + b|_{p} ≤ max{|a|_{p}, |b|_{p}}.

That last inequality is stronger than the triangle inequality |a + b|_{p} ≤ |a|_{p} + |b|_{p}. This absolute value makes ℤ_{p} into a complete metric space (every Cauchy sequence converges), with ℤ^{+} as a dense subset.

Elements of ℤ_{p} are often viewed as series: every c ∈ ℤ_{p} can be expressed as a “power series” c = a_{0} + a_{1}p + a_{2}p^{2} + …, where a_{n} ∈ {0, 1, …, p − 1} for every n ≥ 0. Every such power series ∑ a_{n}p^{n} (with 0 ≤ a_{n} < p) converges relative to the metric above.

Lemma 5.1. For any positive integers b_{1}, b_{2}, b_{3} …, the iterated exponential

E_{j=1}^{∞} b_{j} = b_{1} ↑b_{2} ↑b_{3} ↑… converges in ℤ_{p}.

Proof. Let c_{n} = b_{1} ↑ b_{2} ↑ … ↑ b_{n}. By Corollary 2.11, if s, t > h(p^{m}) then c_{s} ≡ c_{t} (mod p^{m}), that is, |c_{s} − c_{t}|_{p} < p^{−m}. Then {c_{n}} is a Cauchy sequence so its limit exists in ℤ_{p}.

Definition 5.2. If n ∈ ℤ^{+} define α(n) = a^{(p)}(n) = E_{j=1}^{∞}n in ℤ_{p}. We could also write this as

α(n) = n↑↑∞.

Since α(n) = n ↑ n ↑ n ↑ ⋯, it is natural to expect that n^{α(n)} = α(n) in ℤ_{p}. This fails when p|n, because in that case α(n) = 0 in ℤ_{p}. Difficulties arise even when n ≢ 0 (mod p) because it is not clear how to define n^{x} for a p-adic integer x. The function f(x) = n^{x} is defined for x in ℤ, but it might have no continuous extension to the larger ring ℤ_{p}. The next lemma shows that when n ≡ 1 (mod p) there is no obstruction to extending the domain of f(x) = n^{x} from ℤ^{+} to ℤ_{p}.

Lemma 5.3. Suppose a ∈ ℤ_{p} and |a − 1|_{p} < 1. Equivalently, a ≡ 1 (mod p). Suppose x, y ∈ ℤ_{p}.

(1) For m ≥ 1, x ≡ y (mod p^{m}) implies x^{p} ≡ y^{p} (mod p^{m+1}).

(2) If s, t ∈ ℤ^{+} and s ≡ t (mod p^{m}) then a^{s} ≡ a^{t} (mod p^{m+1}).

(3) If x ∈ ℤ_{p}, express x = lim_{n→∞} x_{n} where x_{n} ∈ ℤ^{+}, and define a^{x} = lim a^{x_{n}}. Then a^{x} is well defined, independent of the choice of the sequence {x_{n}}. Moreover, f(x) = a^{x} defines a continuous function ℤ_{p} → ℤ_{p} satisfying:

(4) a^{x+y} = a^{x}a^{y}; a^{x} ≡ 1 (mod p) and (a^{x})^{y} = a^{xy}; |a^{x} − a^{y}|_{p} ≤ \frac{1}{p}|x − y|_{p}.

(5) If a, b ∈ ℤ_{p} and a ≡ b ≡ 1 (mod p) then (ab)^{x} = a^{x}b^{x}.

Sketch of proof. (1) Express y = x + p^{m}t and use the binomial theorem. (2) By (1) we know a^{p^{m}} ≡ 1 (mod p^{m+1}), and the claim follows. Statement (2) is equivalent to: |a^{s} − a^{t}|_{p} ≤ \frac{1}{p}|s − t|_{p}. (3) If \{x_{n}\} is convergent, then \{a^{x_{n}}\} is a Cauchy sequence, so a^{x} is defined. Triangle inequalities yield the inequality in (4) and this helps show that a^{x} is independent of the choice of {x_{n}}. The remaining statements follow similarly.

A more sophisticated approach to these ideas is to introduce p-adic exponential and logarithm functions and then define a^{x} = exp(x log a). Details appear in Borevich-Shafarevich (1966) pp. 285-288 or Koblitz (1977) pp. 75-82. Since log(1 + x) converges on the open unit ball, log(a) is defined only if |a − 1|_{p} < 1. These two definitions of a^{x} coincide because they both are continuous extensions of f(n) = a^{n} on ℤ^{+}, which is dense in ℤ_{p}.

The lemma implies that if n ≡ 1 (mod p) and f(x) = n^{x} then f : ℤ_{p} → ℤ_{p} is a contraction mapping: |f(x) − f(y)|_{p} < \frac{1}{p}|x − y|_{p}. The Banach fixed point theorem states that a contraction mapping f on a complete metric space has a unique fixed point, obtained as lim_{n→∞} f^{n}(c) for any initial point c. Then in our case, this process reflects ideas developed in earlier sections: the unique α ∈ ℤ_{p} satisfying α = n^{α} is obtained from the map f(x) = n^{x} by choosing any c ∈ ℤ_{p} and taking the limit of the iterates f(c) = n ↑ c, ff(c) = n ↑ n ↑ c, fff(c) = n↑n↑n↑c, . . .. This α = α(n) is the unique solution x ∈ ℤ_{p} to x = n^{x}, in the case n ≡ 1 (mod p).

Before considering cases when n ≢ 1, we note that another contraction map appears in Lemma 5.3(1). The map g(x) = x^{p} satisfies: |g(x) − g(y)|_{p} ≤ \frac{1}{p}|x − y|_{p}. However, on closer examination we find that this g isn’t a contraction on the whole space ℤ_{p}, since that inequality fails if x ≢ y (mod p). We can fix this by separating the metric space ℤ_{p} into p parts, S_{b} = {k ∈ ℤ_{p} : k ≡ b (mod p)}. Each S_{b} is a closed subspace of ℤ_{p}, and g(x) = x^{p} is a contraction sending S_{b} to itself. Consequently there is a unique value ω(b) ∈ S_{b} satisfying ω(b)^{p} = ω(b). The uniqueness implies that this value depends only on the residue \overline{b} ∈ ℤ/pℤ. Since ω(0) = 0 we ignore that case and consider ω as a map on the nonzero classes ω : (ℤ/pℤ)^{∗} → ℤ_{p}. It is not hard to check that the image of ω is the group of (p − 1)^{st} roots of unity in ℤ_{p}. This p-adic integer ω(b) = lim_{m→∞} b^{p^{m}} is the “Teichmüller

representative” of the residue class \overline{b}.

When n ≢ 1 (mod p) the function f(k) = n^{k} on ℤ^{+} does not extend continuously to ℤ_{p}. Instead there are p − 1 continuous “branches”, or partial extensions. Since n^{p−1} ≡ 1 (mod p), the powers (n^{p−1})^{x} are well defined for x ∈ ℤ_{p}, by (5.3). We would like to take the (p − 1)^{st} root to define n^{x}, but there are several choices involved.

Following Koblitz (1977) p. 27, if n ≢ 0 (mod p), define ⟨n⟩ = n/ω(n) ∈ ℤ_{p}. Then ⟨n⟩ ≡ 1 (mod p) (so that ⟨n⟩^{x} is well defined) and ⟨n⟩^{p−1} = n^{p−1}. We can now find continuous (p − 1)^{st} roots of (n^{p−1})^{x} by setting f(x) = ζ · ⟨n⟩^{x}, where ζ ∈ ℤ_{p} and ζ^{p−1} = 1. For k ∈ ℤ^{+}, this f(k) equals n^{k} exactly when ζ = ω(n)^{k}. For b ∈ ℤ, this leads to the definition

f_{n,b}(x) = ω(n)^{b}⟨n⟩^{x}.

Then f_{n,b} : ℤ_{p} → ℤ_{p} is continuous, f_{n,b}(x)^{p−1} = (n^{p−1})^{x} for all x, and f_{n,b}(k) = n^{k} for every k ∈ S_{b}. This is the unique function with those properties since S_{b} is dense in ℤ_{p}. The number of different functions here is o_{p}(n), since f_{n,b} depends on n^{b} (mod p).

Proposition 5.4. Suppose n ∈ ℤ^{+} and p ∤ n. Then α(n) is the unique fixed point of the map f_{n,b} when b = α_{p−1}(n).

Proof. f_{n,b} is a contraction since |f_{n,b}(x) − f_{n,b}(y)|_{p} = |⟨n⟩^{x} − ⟨n⟩^{y}|_{p} ≤ \frac{1}{p}|x − y|_{p}. Therefore there is a unique fixed point in ℤ_{p}. For any large t, n ↑↑ t ≡ α_{p−1}(n) ≡ b (mod p − 1).

Therefore n ↑↑ t ∈ S_{b}. Hence E_{t+1}(n) = n ↑ (n ↑↑ t) = f_{n,b}(n ↑↑ t). Now take the limit as t → ∞.

For every b the function f_{n,b} has a unique fixed point in ℤ_{p}. Generally, for a, c ∈ ℤ_{p} with c ≡ 1 (mod p), the function f(x) = a·c^{x} is a contraction with a fixed point β. Then β/a is the fixed point of g(y) = c^{ay}, obtained as the limit c^{a} ↑c^{a} ↑· · ·.

As an application of (5.4) we consider the injectivity of α on ℤ^{+}.

Proposition 5.5. The map α = α^{(p)} : ℤ^{+} → ℤ_{p} sends every multiple of p to 0. On the other positive integers, α^{(p)} is injective.

Proof. If p | n then n ↑ n ↑ … ↑ n involves high powers of p so the limit is 0 in ℤ_{p}. Note that if c ≠ 1 and |c − 1|_{p} < 1 then the map g(x) = c^{x} is injective. (This follows from the p-adic logarithm, but there is a more elementary proof in the style of (5.3).)

Now suppose n, m ∈ ℤ^{+}, n, m ≢ 0 (mod p), and and x = α(n) = α(m) in ℤ_{p}. By (5.4), x = f_{n,b}(x) = f_{m,c}(x) for some b, c. Then x^{p−1} = (n^{p−1})^{x} = (m^{p−1})^{x} in ℤ_{p} and we find that ((nm^{−1})^{p−1})^{x} = 1. With c = (nm^{−1})^{p−1} we have c ≡ 1 (mod p) and c^{x} = 1. The injectivity mentioned above implies c = 1. But then n^{p−1} = m^{p−1} in ℤ, so that n = m.

We have been considering towers of powers in ℤ_{p}. However it is perhaps more natural to consider those limits without restricting to a single prime p. Whenever d|k there is a natural reduction map π_{k,d} : ℤ/kℤ → ℤ/dℤ, and the projective limit makes sense: ℤ̂ = \underleftarrow{lim}(ℤ/kℤ). An element ĉ ∈ ℤ̂ is defined to be a sequence ĉ = (c_{1}, c_{2}, …) with c_{k} ∈ ℤ/kℤ satisfying the “coherence” condition: if d | k then π_{k,d}(c_{k}) = c_{d}. Unique factorization and the Chinese Remainder Theorem provide a ring isomorphism:

ℤ̂ ⟶^{≅} ∏_{p} ℤ_{p},

where the direct product is taken over all primes p. Elements of ℤ̂ can also be thought of as “profinite integers” as described using factorial representations in Lenstra’s paper [18].

If {a_{n}} is a sequence in ℤ^{+}, then by (2.11), the numbers c_{n} = a_{1} ↑a_{2} ↑…↑a_{n} define an

element ĉ = E_{j=1}^{∞} a_{j} ∈ ℤ̂. In particular, for n ∈ ℤ^{+} we have an element α̂(n) = E_{j=1}^{∞} n = n↑n↑

n↑⋯ in ℤ̂, which induces the element α^{(p)}(n) ∈ ℤ_{p} for every prime p. The domain of α̂ can be enlarged to include all n̂ ∈ ℤ̂ by just taking the limit of the maps \overline{α}_{k} : ℤ/L(k)ℤ → ℤ/kℤ defined in §2 to build α̂ : ℤ̂ → ℤ̂. That is, if ĉ = (c_{1}, c_{2}, …), we define α̂(ĉ) by setting

α̂(ĉ)_{k} = \overline{α}_{k}(c_{L(k)}).

By (5.5) it follows that the restriction α̂ : ℤ^{+} → ℤ̂ is injective. However α̂ is not injective on ℤ̂. To see this, note that any ĉ ∈ ℤ̂ is determined by its list of components c^{(p)} ∈ ℤ_{p}. Define ĉ by requiring c^{(p)} = p for every p. Check that ĉ ≠ 0 but α̂(ĉ) = 0.

To extend our work with p-adic numbers, we would like to define exponential functions and consider their fixed points. Starting at the finite level, define an exponential map

expon_{k} : (ℤ/kℤ) × (ℤ/λ(k)ℤ) → (ℤ/kℤ) by: expon_{k}(\overline{a}, \overline{b}) = \overline{a^{b}}.

This can be a bit confusing since b is a residue class (not an integer) and the value \overline{a^{b}} corresponds to a term in the “cycle” part of the sequence 1, a, a^{2}, a^{3}, …. For instance, when k = 40 the powers of 2 (mod 40) are: 1, 2, 4, 8, 16, 32, 24, 8, 16, …. Since λ(40) = 4, we find that expon_{40}(\overline{2}, \overline{1}) = \overline{2}\overline{1} = \overline{32} in ℤ/40ℤ, since that’s the term in the cycle corresponding to 1 (mod 4).

Now take the limit of those maps expon_{k} as k → ∞, to obtain expon : ℤ̂ × ℤ̂ → ℤ̂. We can write expon(â, b̂) as âb̂, but repeat the warning about interpretations. Although ℤ embeds as a subring of ℤ̂, this exponential map isn’t consistent with traditional exponents of integers. For example, 1 and 2 embed as constant sequences ˆ1, ˆ2 in ℤ̂, but ˆ2ˆ1 does not match 2^{1} in ℤ.

One interesting point is that this exponential map generalizes all the p-adic exponential maps, but without the concerns about convergence. The point is that defining a^{x} for a ∈ ℤ/p^{m}ℤ requires the exponent x to live in ℤ/p^{m−1}(p−1)ℤ ≅ ℤ/p^{m−1}ℤ×ℤ/(p−1)ℤ. Ignoring the (ℤ/(p−1)ℤ)-component of x leads to p−1 different branches of the exponential function. In ℤ̂ those components are not ignored and that difficulty vanishes.

Not surprisingly, the analysis of functions on ℤ̂ present various difficulties not arising in ℤ_{p}. It should be interesting to investigate whether the exponential maps on ℤ̂ are contractions relative to some nice metric, and whether α̂(n) is the unique fixed point of the function f(x̂) = nx̂. We leave further development of this theory to the reader.

6. Some Problems

Here are a few open problems related to topics discussed above.

By (2.11) for given k every sequence n, n^{n}, n^{n^{n}}, n ↑↑ 4, … (mod k) becomes stable after at most h(k) + 1 steps.

Problem 6.1. How fast does the height function h(k) grow?

The corresponding question for the φ-height has been studied. In analogy to Definition 2.10 let the φ-height be h_{φ}(k) = min{s : φ^{s}(k) = 1}. In 1943 H. N. Shapiro [24] proved that h_{φ}(k) has multiplicative properties and grows logarithmically. Does h(k) have the same order of magnitude as h_{φ}(k)? See H. N. Shapiro [25] , Parnami [21] and Erdős and Graham [12] pp. 80-81 for related questions.

Rather than considering all n simultaneously, define a height for each n:

ℓ_{k}(n) = min{t : E_{t}(n) ≡ E_{t+1}(n) (mod k)}

For given n, k, note that the sequence E_{t}(n) (mod k) stabilizes after ℓ_{k}(n) steps:

Lemma 6.2. If E_{t−1}(n) ≡ E_{t}(n) (mod k) then E_{t}(n) ≡ E_{t+1}(n) (mod k).

Proof. To prove that E_{t}(n) − E_{t−1}(n) divides E_{t+1}(n) − E_{t}(n) for every n, check that (n^{a} − a)|(n^{b} − b) ⟹ (n^{n^{a}} − n^{a})|(n^{n^{b}} − n^{b}).

Consequently, ℓ_{k}(n) ≤ h(k). Since ℓ_{k}(n) = 1 + ℓ_{o_{k}(n)}(n) it follows that if s and L(k) are coprime then ℓ_{k}(n^{s}) = ℓ_{k}(n).

Problem 6.3. Investigate ℓ_{k}(n). As n varies, how do the values ℓ_{k}(n) compare with h(k)?

Let N_{t}(a mod k) be the number of solutions to E_{t}(x) ≡ a (mod k), counted in one period. In (4.3) we proved that N_{t}(a mod k) > 0 whenever a is a unit. In some cases when (ℤ/kℤ)^{∗} is cyclic, there is an explicit formula for N_{2}. For instance, if p is an odd prime and a is coprime to p then

N_{2}(a mod p^{m}) = ∑_{d| \frac{p−1}{r}}d φ(\frac{p − 1}{d}),

where r = o_{p}(a). The proof involves choosing a generator g and counting x values by tabulating s, t such that x ≡ g^{t} (mod p^{m}) and x ≡ s (mod p^{m−1}(p − 1)) such that x^{x} ≡ g^{st} ≡ a (mod p^{m}). Details are omitted.

Problem 6.4. Given k, for which a is there a solution to x^{x} ≡ a (mod k)? How about E_{t}(x) ≡ a (mod k)? More generally, is there a simple formula for N_{t}(a mod k)? For these questions, we consider only those x lying in the cyclic part, ℤ/L_{t}(k)ℤ.

Most of the information derived so far about the image of E_{t} in ℤ/kℤ is independent of t. In addition to Lemma 6.2, we make another small observation relating these images for different t values:

If E_{t}(n) ≡ 1 (mod k) then E_{t+1}(n) ≡ 1 (mod k).

To see this note that (E_{t}(n) − 1) | (E_{t+1}(n) − 1), since a|b ⟹ (n^{a} − 1)|(n^{b} − 1).

Problem 6.5. As t varies, how are the sets image(E_{t}) ⊂ ℤ/kℤ related?

Approximations to α(n) = α^{(p)}(n) ∈ ℤ_{p} can be easily computed, but not much is known about its algebraic properties. We note that α(n) ∉ ℚ:

If 1 < n ∈ ℤ^{+} and p ∤ n then α(n) is irrational. For if α(n) = r/s in lowest terms, then by (5.4), (r/s)^{p−1} = (n^{p−1})^{r/s} in ℤ_{p}. This implies r^{(p−1)s} = n^{(p−1)r}s^{(p−1)s} in ℤ. But that equation yields s = 1 and r = n^{r}, a contradiction.

Problem 6.6. For n as above, is α^{(p)}(n) ∈ ℤ_{p} transcendental over the field ℚ of rational numbers?

For any sequence {a_{1}, a_{2}, a_{3}, … } in ℤ^{+}, the limit E_{j=1}^{∞} a_{j} = a_{1}^{a_{2}^{·^{·^{·}}}} is a well-defined element in ℤ̂, the ring of profinite integers. If {b_{n}} is a different sequence in ℤ^{+}, it can happen that E_{j=1}^{∞} a_{j} = E_{j=1}^{∞} b_{j} in ℤ̂. Examples are easy to produce when some a_{i}, b_{j} are allowed to equal 1. For instance, 2^{4^{5}} = 4^{2^{3^{2}}} and 9^{2^{3}} = 3^{2^{2^{2}}}. Examples of such equalities seem to be harder to find with infinite towers. Problem 6.7. Suppose a_{1}, a_{2}, a_{3}, … and b_{1}, b_{2}, b_{3}, … are sequences in ℤ^{+} and every a_{i}, b_{i} ≥ 2. If E_{j=1}^{∞} a_{j} = E_{j=1}^{∞} b_{j} in ℤ̂, does it follow that every a_{i} = b_{i}?

References

[1] Joel Anderson, Iterated exponentials, Amer. Math Monthly. 111 (2004) pp. 668-679.

[2] I. N. Baker and P. J. Rippon, A note on complex iteration, Amer. Math. Monthly 92 (1985), pp. 501-504.

[3] G. R. Blakley and I. Borosh, Modular arithmetic of iterated powers, Comput. Math. Appl. 9 (1983) pp. 567-581.

[4] Z. I. Borevich and I. R. Shafarevich, Number Theory, Academic Press, 1966.

[5] N. Bromer, Superexponentiation, Math. Mag. 60 (1987) pp. 169-174.

[6] R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), pp. 232-238.

[7] R. Crocker, On a new problem in number theory, Amer. Math. Monthly 73 (1966) pp. 355-357.

[8] R. Crocker, On residues of n^{n}, Amer. Math. Monthly 76 (1969) pp. 1028-1029.

[9] A. C. Cunningham, On hyper-even numbers and on Fermat’s numbers, Proc. London Math. Soc. (2) 5 (1907) pp. 237-274.

[10] Robert J. MacG. Dawson, Towers of powers modulo m, College. Math. J. 25 (1994) pp. 22-28.

[11] A. Ecker, Comment on the note: “The congruence a^{r+s} ≡ a^{r} (mod m)” by A. Livingston and M. L. Livingston, Amer. Math. Monthly 87 (1980) pp. 811-814.

[12] P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographie no. 28 de L’Enseignement Mathmatique, Geneva, 1980.

[13] R. Hampel, The length of the shortest period of rests of number n^{n}, Ann. Polon. Math. 1 (1955) pp. 360-366.

[14] R. A. Knoebel, Exponentials reiterated, Amer. Math. Monthly 88 (1981), pp. 235-252.

[15] D. E. Knuth, Coping with finiteness, Science 194 (1976), pp. 1235-1242.

[16] N. Koblitz, p-adic Numbers, p-adic Analysis, and Zeta-Functions, Graduate Texts in Math. vol. 58, Springer-Verlag, 1977.

[17] N. Koblitz, p-adic Analysis: a Short Course on Recent Work, London Math. Soc. Lecture Note Series v. 46, Cambridge Univ. Press, 1980.

[18] H. Lenstra, Profinite Fibonacci numbers, Nieuw Arch. Wiskd. (5) 6 (2005) 297-300.

[19] A. E. Livingston and M. L. Livingston, The congruence a^{r+s} ≡ a^{r} (mod m), Amer. Math. Monthly 85 (1978) pp. 97-100.

[20] H. Maurer, Über die Funktion x^{[x^{(x^{(.^{.^{.}})})}]} für ganzzahliges Argument (Abundanzen), Mittheilungen der Mathematische Gesellschaft in Hamburg 4 (1901), pp. 33-50.

[21] J. C. Parnami, On iterates of Euler’s φ-function, Amer. Math. Monthly 74 (1967) pp. 967-968.

[22] A. Schinzel and W. Sierpiński, Sur les congruences x^{x} ≡ c (mod m) et a^{x} ≡ b (mod p), Collect. Math. 11 (1959) pp. 153-164.

[23] D. B. Shapiro, Comment on problem 559, Crux Math. 13 (1987) pp. 291-294.

[24] H. N. Shapiro, An arithmetic mean arising from the ϕ function, Amer. Math. Monthly 50 (1943) pp. 18-30.

[25] H. N. Shapiro, On the iterates of a certain class of arithmetic functions, Comm. Pure Appl. Math. 3 (1950) pp. 259-272.

[26] H. N. Shapiro, Introduction to the Theory of Numbers, John Wiley and Sons, 1983.

[27] W. Sierpiński, Sur les puissances du nombre 2, Ann. Soc. Polon. Math. 23 (1950) pp. 246-251.

[28] W. Sierpiński, Sur la périodicité mod m de certaines suites infinies d’entiers, Ann. Soc. Polon. Math. 23 (1950) pp. 252-258.

[29] D. Singmaster, A maximal generalization of Fermat’s theorem, Math. Magazine 39 (1966) pp. 103-107.

[30] I. M. Vinogradov, Elements of Number Theory, Dover, 1954.

[31] Problem A - 4 in: 1985 Putnam Competition, Math. Mag. 59 (1986) pp. 123-126.

[32] Problem 3 in: Twentieth Annual U.S.A. Mathematical Olympiad, Math. Mag. 65 (1992) pp. 205 - 206.