On the Equation a^{x} ≡ x (mod b^{n})

J. Jiménez Urroz and J. Luis A. Yebra Departament de Matemàtica Aplicada IV Universitat Politècnica de Catalunya Campus Nord, Edifici C3 C. Jordi Girona, 1-3 08034 Barcelona Spain

                 jjimenez@ma4.upc.edu
                   yebra@ma4.upc.edu

Abstract

We study the solutions of the equation a^{x} ≡ x (mod b^{n}). For some values of b, the solutions have a particularly rich structure. For example, for b = 10 we find that for every a that is not a multiple of 10 and for every n ≥ 2, the equation has just one solution x_{n}(a). Moreover, the solutions for different values of n arise from a sequence x(a) = {x_{i}}_{i≥0}, in the form x_{n}(a) = ∑_{i=0}^{n−1} x_{i}10^{i}. For instance, for a = 8 we obtain

8^{56} ≡ 56 (mod 10^{2}) ,  8^{856} ≡ 856 (mod 10^{3}) ,  8^{5856} ≡ 5856 (mod 10^{4}) , …

In this paper we prove these results and provide sufficient conditions for the base b to have analogous properties.

1 Introduction

The fact that 7^{343} ends in 343 might appear to be a curiosity. However, when this can be uniquely extended to

7^{630680637333853643331265511565172343} = ⋯ 630680637333853643331265511565172343,

and more, it begins to be interesting. Besides, instead of 7, any other positive integer a (as long as it is not a multiple of 10) will do. For instance, for a = 12, we find

12^{52396359135848584931714421454012416} = ⋯ 52396359135848584931714421454012416.

More precisely, we prove below that for any positive integer a, not a multiple of 10, there exists just one infinite sequence of digits,

x(a) = ⋯ x_{i} ⋯ x_{2} x_{1} x_{0}

such that for every n ≥ 2 the number

x_{n}(a) = ∑_{i=0}^{n−1} x_{i}10^{i} = x_{n−1} ⋯ x_{2}x_{1}x_{0}

is the only such number that satisfies

a^{x_{n}(a)} ≡ x_{n}(a) (mod 10^{n}) .  (1)

Moreover, this result holds not just for base b = 10; an analogous result holds when b is squarefree and such that for every prime p|b and every prime q|p − 1 we have q|b.

For any positive integer a, not a multiple of b, there exists an infinite sequence of b-digits,

x(a, b) = (⋯ x_{i} ⋯ x_{2} x_{1} x_{0})_{b}

such that for every n ≥ n(b), which is characterized below, the number

x_{n}(a, b) = ∑_{i=0}^{n−1} x_{i}b^{i} = (x_{n−1} ⋯ x_{2} x_{1} x_{0})_{b}

satisfies

a^{x_{n}(a,b)} ≡ x_{n}(a, b) (mod b^{n}) .  (2)

For instance, for b = 6 and a = 4 we have

x(4, 6) = ⋯ 3211201450455542325540435055354110453104_{6},

so that when, say, n = 11, we get

x_{11}(4, 6) = 54110453104_{6} = 344639488 and 4^{344639488} ≡ 344639488 (mod 6^{11}) .

When the base b is not squarefree, instead of multiples of b, we must remove any multiple of s(b), the squarefree part of b, for obvious reasons.

Finally, the conditions described above are suffcient to guarantee the existence of at least one such sequence x(a, b), but they are not necessary. It might be the case that for some other base b and some value of a there exist a sequence x(a, b) as above. As an example we have for b = 9 and a = 4 the sequence x(4, 9) = ⋯ 4444444_{9}.

2 Main results

We only use elementary number theory and refer to Hardy and Wright [1] or Riesel [2] for any concept not defined here. We will write the prime factorization of an integer b as b = ∏_{p} p^{v_{p}(b)}, and denote by e(b) = max_{p|b}{v_{p}(b)}, the highest power of a prime dividing b. We will also denote s(b) = ∏_{p|b} p the squarefree part of b.

Theorem 1. For every pair of integers a, b there exists an integer x ≥ e(b) + 1 such that

a^{x} ≡ x (mod b).

For the proof we will need the following observation.

Lemma 2. Let a, b integers and x ≥ e(b) a solution to the equation

a^{x} ≡ x (mod φ(b)).

Then

a^{a^{x}} ≡ a^{x} (mod b).

Proof: Let b = b_{1}b_{2} where gcd(b_{1}, a) = 1 and if p|b_{2} then p|a. Then φ(b_{1})|φ(b) and, hence, a^{x} ≡ x (mod φ(b_{1})). It is now a simple consequence of Euler´ s theorem to get

a^{a^{x}} ≡ a^{x} (mod b_{1}) .

On the other hand, we trivially have

a^{a^{x}} ≡ a^{x} ≡ 0 (mod b_{2}) .

The result now follows from the Chinese Remainder Theorem.

Proof of Theorem 1: We proceed by induction on b, noting that the result is trivial for b = 1, 2. Let us suppose we have already proven the theorem for every integer less than b and we want to prove the result for b. We will also suppose a > 1. Now, noting that φ(b) < b we can apply induction to obtain a solution x ≥ e(φ(b)) + 1 to the equation

a^{x} ≡ x (mod φ(b)) .

In this case, since e(φ(b)) ≥ e(b) − 1 by definition, we can apply Lemma 2 to get

a^{a^{x}} ≡ a^{x} (mod b) .

Now, noting that a^{x} = (1 + (a − 1))^{x} = ∑_{j=0}^{x} \binom{x}{j}(a − 1)^{j} ≥ 1 + x for any integers a > 1 and x ≥ 0, we get a^{x} ≥ x + 1 ≥ e(b) + 1, as desired.

Definition: We say that an integer b is a valid base if for every prime p|b and every prime q|p − 1 we have q|b. We will let n(b) be the minimum integer such that (p − 1)|b^{n(b)} for every p|b.

Remarks: The existence of such an integer n(b) is clear from the definition of valid base. It is straightforward to see that a valid base b must be even. It is also easy to see that b = 2, 4, 6, 8, 10, 12, 16, 18, 20, 24, and 30 are the first valid bases while b = 2, 6, 10, 30, 34, 42, 78, 102 and 110 are the first valid squarefree bases. Observe also that when b is squarefree, n(b) = max_{p|b}{max_{q|b}{v_{q}(p − 1)}}. Thus, we have n(10) = 2 and n(34) = 4, while n(100) = 1.

Apart from the bases given in this Remark, one can ask whether there exist other valid bases and how to find them. The following list provides different ways of constructing new valid bases. In particular we note the existence of infinitely many valid bases.

• The product of valid bases is a valid base.

• If b is a valid base and p is a prime such that p − 1|b^{r}, for some r, then pb is also a valid base.

• b = m! is a valid base for every m.

• For every integer r, b = ∏_{p≤r} p is a valid base.

The first two statements are direct consequences of the definition. For the third and fourth we just have to note that if p|b and q|p − 1, then q ≤ m in the third statement, while q ≤ r in the last one.

The main result, where we denote the number x_{n}(a, b) by x_{n} for short, follows.

Theorem 3. Let b be a valid base, and s(b) its squarefree part. Then, for every integer a not a multiple of s(b) there exist a unique sequence {c_{n}}_{n≥n_{b}} of digits, 0 ≤ c_{n} < b, such that the integers x_{n+1} = x_{n} + c_{n}b^{n} verify

a^{x_{n}} ≡ x_{n} (mod b^{n}),

for every n > n(b).

Proof: To clarify the argument, we first present the case when b is a squarefree integer. In all the cases below, we will proceed by induction on n.

Case I: b is squarefree and gcd(a, b) = 1.

Suppose that for some n ≥ n(b)

a^{x_{n}} ≡ x_{n} (mod b^{n}) .

(Observe that we know this is true for n = n(b) by Theorem 1 with b^{n(b)} instead of b). Then,

a^{x_{n}} ≡ x_{n} + c_{n}b^{n} (mod b^{n+1}) ,

for some 0 ≤ c_{n} < b. Now, it is immediate to observe that for a valid base it is always true that φ(p^{n+1})|b^{n} for every integer n ≥ n(b) and every prime p|b. Hence, since a^{φ(p^{n+1})} ≡ 1 (mod p^{n+1}), we have, for every integer m

a^{mb^{n}} ≡ 1 (mod b^{n+1}) ,

by the Chinese Remainder Theorem. In particular

a^{x_{n}+c_{n}b^{n}} ≡ a^{x_{n}} (mod b^{n+1}) ≡ x_{n} + c_{n}b^{n} (mod b^{n+1}) ,

that is

a^{x_{n+1}} ≡ x_{n+1} (mod b^{n+1}) ,

and the selection of c_{n} is unique.

Case II: b is squarefree and gcd(a, b) > 1.

Let b = b_{1}b_{2} be such that gcd(b_{1}, a) = 1, and b_{2}|a. Again the proof proceeds by induction, and we suppose

a^{x_{n}} ≡ x_{n} (mod b^{n}) ≡ x_{n} + c_{n}b^{n} (mod b^{n+1}) ,  (3)

for n ≥ n(b). In this case, and in the same way as before, we have for every integer m

a^{mb^{n}} ≡ 1 (mod b_{1}^{n+1}) ,

since gcd(a, b_{1}) = 1. In particular

a^{x_{n}+c_{n}b^{n}} ≡ a^{x_{n}} (mod b_{1}^{n+1}) ≡ x_{n} + c_{n}b^{n} (mod b_{1}^{n+1}) .

On the other hand, it is easy to see that b_{2}^{n+1}| gcd(a^{x_{n}+c_{n}b^{n}}, x_{n} + c_{n}b^{n}). Indeed, if x_{n} ≥ n + 1 then trivially b_{2}^{n+1}|a^{x_{n}+c_{n}b^{n}} and b_{2}^{n+1}| gcd(a^{x_{n}}, b^{n+1}). Hence, b_{2}^{n+1} divides x_{n} + c_{n}b^{n} by (3). Furthermore, x_{n} > 0 and so, again by (3), we can see that b_{2}^{n}|x_{n} and, in particular, x_{n} ≥ n+1. Hence,

a^{x_{n}+c_{n}b^{n}} ≡ x_{n} + c_{n}b^{n} (mod b_{2}^{n+1}) ,

and the result follows from the Chinese Remainder Theorem.

Case III: b is not squarefree and gcd(a, b) = 1.

Let b = ∏ p^{v_{p}(b)} = P_{1}^{α_{1}} ⋯ P_{r}^{α_{r}} where α_{1} < α_{2} < ⋯ < α_{r} and P_{i} are squarefree for i = 1, …, r. We will also denote B_{j} = ∏_{i=1}^{j−1} P_{i}^{α_{i}}, and B_{1} = 1. Suppose again

a^{x_{n}} ≡ x_{n} (mod b^{n})

for some n ≥ n(b). Then

a^{x_{n}} ≡ x_{n} + c_{1,1,n}b^{n} (mod P_{1}b^{n}) ,

and 0 ≤ c_{1,1,n} < P_{1}. Again, as before, φ(p^{nv_{p}(b)+1})|b^{n} for any n ≥ n(b) and p|P_{1}, so that, arguing as before, we get that for any integer m

a^{mb^{n}} ≡ 1 (mod P_{1}b^{n}) .

In particular,

a^{x_{n}+c_{1,1,n}b^{n}} ≡ a^{x_{n}} (mod P_{1}b^{n}) ≡ x_{n} + c_{1,1,n}b^{n} (mod P_{1}b^{n}) .

Repeating this process, and noting that φ(p^{nv_{p}(b)+i})|P_{1}^{i−1}b^{n}, we get

a^{x_{n,1}} ≡ x_{n,1} (mod P_{1}^{α_{1}}b^{n}) ,  (4)

for a unique

x_{n,1} = x_{n} + ( ∑_{i=0}^{α_{1}−1} c_{i,1,n}P_{1}^{i}) b^{n},

where 0 ≤ c_{i,1,n} < P_{1}. Now we just have to note that for any 1 ≤ l ≤ r and any j_{l} < α_{l} we have φ(p^{nv_{p}(b)+j_{l}})|P_{l}^{j_{l}−1}B_{l}b^{n}. By iterating the previous process, we can then build a unique

x_{n+1} = x_{n} + (∑_{j=1}^{r} ∑_{i=0}^{α_{j}−1} c_{i,j,n}P_{j}^{i}B_{j}) b^{n},

where c_{i,j,n} ≤ P_{j} − 1, such that

a^{x_{n+1}} ≡ x_{n+1} (mod b^{n+1}) .

Hence, since

∑_{j=1}^{r} ∑_{i=0}^{α_{j}−1} c_{i,j,n}P_{j}^{i}B_{j} ≤ ∑_{j=1}^{r}(P_{j} − 1) ∑_{i=0}^{α_{j}−1} P_{j}^{i}B_{j} = ∑_{j=1}^{r}(P_{j}^{α_{j}} − 1)B_{j} = ∑_{j=1}^{r}(B_{j+1} − B_{j}) = b − 1,

the result follows.

Case IV: b is not squarefree and gcd(a, b) > 1.

The proof is now the same as in Case II and we omit it.

Remark: It is very important to notice that, whenever n ≥ n(b), even if the solution guaranteed by Theorem 1 is x ≥ b^{n}, we can find another one y < b^{n}. Hence, for any integer n ≥ n(b) the integer x_{n} indeed gives the n first digits in base b of the integer x_{m} for every m ≥ n. To see this, observe that if

a^{x} ≡ x (mod b^{n}) ,

and x > b^{n}, then x = ∑_{i=0}^{n−1} c_{i}b^{i} + ∑_{i=n}^{k} c_{i}b^{i} = y + b^{n}Y for some y ≠ 0, since otherwise a is a multiple of s(b). But then,

y ≡ 0 (mod b_{2}^{n}) ,

since a^{x} ≡ 0 (mod b_{2}^{n}) and a^{x} ≡ y (mod b_{2}^{n}). But then, y ≥ b_{2}^{n} ≥ e(b_{2})n, and we also have

a^{y} ≡ 0 ≡ y (mod b_{2}^{n}) .

Finally, since n ≥ n(b), a^{b^{n}} ≡ 1 (mod b_{1}^{n}), and so

a^{y} ≡ y (mod b_{1}^{n}) .

The result is now a consequence of the Chinese Remainder Theorem.

Besides, it is easily verified that when b = 10 there is just one solution y < 10^{n(10)} = 100 for every a (not a multiple of 10), since it suffices to check values of a mod 100. Thus there is a unique sequence x(a) for every a. Although this seems to be the case for all valid bases b, it does not follow from Theorem 1.

Corollary 4. If b is a valid base, for every integer a, not a multiple of s(b), there exist a sequence {x_{n}}_{n≥0} of digits 0 ≤ x_{n} < b such that the integers

x_{n}(a, b) = ∑_{i=0}^{n−1} x_{i}b^{i} = (x_{n−1} ⋯ x_{2} x_{1} x_{0})_{b}

verify

a^{x_{n}(a,b)} ≡ x_{n}(a, b) (mod b^{n}),  (2)

for every n ≥ n(b). When b is squarefree, s(b) = b and this holds for every integer a, not a multiple of b. For b = 10 there exists just one such sequence x(a).

3 Other bases

As we mentioned in the introduction, Corollary 4 uses sufficient conditions for the base b to ensure the existence of a sequence x(a, b) for any nontrivial integer a. When b is not a valid base, however, a sequence x(a, b) can still appear for some integers a. Indeed, as we can see in the proof of Theorem 3, the only condition needed is that a^{c_{n}b^{n}} ≡ 1 (mod b^{n+1}) holds. This is true for any valid base, but we can build many other examples for invalid bases. For example, consider an integer b and let m|b − 1 such that m^{b} ≡ −1 (mod b), and let a = m^{m}. Then it is easy to see by induction that m^{b^{r}} ≡ −1 (mod b^{r}) for any r, and so

ma^{^{\frac{b−1}{m}} ∑{n−1 \atop i=0} b^{i}} = m^{b^{n}} ≡ −1 (mod b^{n}) .

On the other hand

m (\frac{b − 1}{m}) ∑_{i=0}^{n−1} b^{i} = b^{n} − 1 ≡ −1 (mod b^{n}) ,

and so x(a, b) = \overline{(\frac{b−1}{m})}_{b} is the desired sequence which provides a solution to the equation a^{x_{n}} ≡ x_{n} (mod b^{n}) for every n. The example at the end of the introduction, x(4, 9) = ¯4_{9}, is a particular case of this example with m = 2, b = 9. Also this framework allows us to prove the following simple example Corollary 5. Let b > 1 an odd integer and a = (b − 1)^{b−1}. Then

a^{x_{n}} ≡ x_{n} (mod b^{n}),

for any n and x_{n} = ∑_{i=0}^{n−1} b^{i}. In other words, x(a, b) = ¯1_{b}.

4 Acknowledgments

This work was partially supported by Secretaría de Estado de Universidades e Investigación del Ministerio de Educación y Ciencia of Spain, DGICYT through grants MTM2006-15038-C02-02, TSI2006-02731 and MTM2009-11068 for the first author and TEC2005-03575 for the second author. It was done while the first author was visiting CRM at Montreal, and he wishes to thank this institute for its hospitality. Finally, the authors want to thank M. C. Muñoz Lecanda.

References

[1] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 2008.

[2] H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhauser, 1994.

2000 Mathematics Subject Classification: Primary 11A07. Keywords: exponential, congruences, integer sequences.

(Concerned with sequences \underline{A133612}, \underline{A133613}, \underline{A133614}, \underline{A133615}, \underline{A133616}, \underline{A133617}, \underline{A133618}, \underline{A133619}, \underline{A144539}, \underline{A144540}, \underline{A144541}, \underline{A144542}, \underline{A144543}, \underline{A144544}, \underline{A151999}, and \underline{A152000}.)

Received June 10 2009; revised version received November 18 2009. Published in Journal of Integer Sequences, November 25 2009.

Return to Journal of Integer Sequences home page.