New York Journal of Mathematics

New York J. Math. 12 (2006) 39–45.

Prime factors of a^{f(n)} − 1 with an irreducible polynomial f(x)

Christian Ballot and Florian Luca

Abstract. In this note, we show that if a is an integer not 0 or ±1 and f(X) ∈ ℚ[X] is an integer valued irreducible polynomial of degree d ≥ 2, then the set of primes p dividing a^{f(n)} −1 for some positive integer n is of (relative) asymptotic density zero.

Contents

1. Introduction 39 2. The proof 40 3. An application 43 References 44

1. Introduction

Let a be an integer not 0 or ±1. For any integer n prime to a we write ℓ_{a}(n) for the order of a as an element of the group (ℤ/nℤ)^{∗}.

In recent years, partly motivated by cryptographic demands, several authors have investigated the arithmetic structure of the numbers ℓ_{a}(n), when n ranges either over all the positive integers, or only over the set of prime numbers. For example, the prime numbers p such that ℓ_{a}(p) is square-free have been investigated by Pappalardi in [6], while the set of primes p such that ℓ_{a}(p) is smooth have been investigated by Pomerance and Shparlinski in [7]. Recall here that a positive integer n is called smooth if its largest prime factor q is small; i.e., if the ratio log q/ log n is small.

In this paper, we fix an integer a different from 0 and ±1 and an irreducible polynomial f(X) ∈ ℚ[X] of degree d ≥ 2 which is integer valued and of positive leading term, and we study the set of prime factors of the numbers u_{n} = a^{f(n)}−1 as

39^{ISSN 1076-9803/06}

Received October 20, 2005.

Mathematics Subject Classification. 11N37, 11B37.

Key words and phrases. Prime factors, linear recurrences, Chebotarev Density Theorem.

This paper was written during a very enjoyable visit by the second author to the Laboratoire Nicolas Oresme of the University of Caen; he wishes to express his thanks to that institution for its hospitality and support. He was also partly supported by grants SEP-CONACYT 46755, PAPIIT IN104505 and a Guggenheim Fellowship.

n ranges over the set of positive integers. Note that such primes p are precisely the ones for which the congruence f(n) ≡ 0 (mod ℓ_{a}(p)) admits one (hence, infinitely many) positive integer solutions n. Our main result shows, perhaps not unexpectedly, that most prime numbers do not divide u_{n} for any value of the positive integer n.

For a positive real number x we write

U_{f}(x) = {p ≤ x : p | a^{f(n)} − 1 for some positive integer n} .

Theorem 1. Let f(X) ∈ ℚ[X] be an integer valued irreducible of degree d ≥ 2. There is a constant r_{f} > 0 such that for every ε > 0 there exists x_{ε} > e^{e} such that

♯U_{f}(x) < \frac{x}{log x(log log log x)^{r_{f} −ε}} for x > x_{ε}.

In particular, ♯U_{f}(x) = o(π(x)) as x → ∞.

The constant r_{f} is the asymptotic density of primes p that divide some f(n), where n is a natural number. Bounds for r_{f} are given in terms of the degree d in Lemma 3.

We do not address the problem of determining a lower bound for ♯U_{f}(x). But at least note that ♯U_{f}(x) → ∞ as x → ∞, since by the Primitive Divisor Theorem, for n large enough there is always a prime factor p of a^{n} − 1 which does not divide a^{m} −1 for any m < n. Taking this assertion through the set of values of f(n) proves our statement.

Under the Generalized Riemann Hypothesis, the log log log x appearing on the right-hand side of the inequality from Theorem 1 can be replaced by log log x. However, since the constant r_{f} is less than 1, the resulting bound on U_{f}(x) is not even strong enough to lead to the conclusion that the sum of the reciprocals of the primes in U_{f} is convergent. We give no details in this direction.

Throughout this paper, we use the Vinogradov symbols ≫ and ≪ and the Landau symbols O and o with their regular meanings. The constants implied by them may depend on the given integer a and polynomial f(X). For a set A of positive integers we put A(x) = A ∩ [1, x]. Some remarks having to do with primes dividing two consecutive terms of cubic integral linear recurring sequences whose associated polynomial has integer roots are presented in Section 3 as an application of Theorem 1.

Acknowledgements. The first author is thankful to Michael Filaseta for sharing some insight on primes that divide two consecutive terms of the sequence a_{n} = 2 · 3^{n} − 3 · 2^{n} + 1 at the West Coast Number Theory Conference of 1993. The authors are grateful to the referee for a fast appreciation of the paper.

2. The proof

The following lemma plays a crucial rôle in our proof and is a special instance of Theorem 1.3 in [6], where we have replaced the function Li(x) by π(x). This is justified since we know that

Li(x) = π(x) (1 + O (exp(−c\sqrt{log x}))) ,

prime factors of a^{f(n)} − 1 41

with some constant c > 0, and certainly

exp(−c\sqrt{log x}) = o ((log x)^{−1/8}) as x → ∞.

Lemma 2. Assume that a > 1 is not the k-th power of an integer for any k ≥ 2. Let m be an odd positive integer and x be a positive integer. Consider the set

A(x, m) = {p ≤ x : m | ℓ_{a}(p)}.

Then, for every ε > 0, the estimate

♯A(x, m) = κ_{m} (1 + O (\frac{m^{1−2ε}}{(log x)^{1/8−ε}} )) π(x) (1)

holds uniformly in m and x where

κ_{m} = \frac{1}{m} ∏_{l|m} \frac{l^{2}}{l^{2} − 1}, (l prime). (2)

We point out that Theorem 1.3 in [6] is more general since it covers the cases when m is even or a is a power of a positive integer. Note also that particular instances of Lemma 2 have appeared previously in works of Odoni [8], Ballot [1], p. 32, and Wiertelak [10].

We will also need the following well-known consequence of Chebotarev’s Density Theorem. To be precise, it only requires the Kronecker and the Frobenius Density Theorems [5], [4], both of which being corollaries of the later, and now famous, Chebotarev Density Theorem, originally conjectured by Frobenius. The theorem we attribute to Kronecker appears in [5] as a consequence of an actual theorem, provided the existence of the densities δ_{i} is assumed. This existence was first shown by Frobenius.

Let f(X) ∈ ℚ[X] be irreducible of degree d ≥ 2. Let

R_{f} = {p : f(n) ≡ 0 (mod p) does not admit an integer solution n}.

Lemma 3. The set R_{f} has a positive (relative) asymptotic density r_{f}. Furthermore, r_{f} is a rational number in the interval [(d − 1)/d!, 1 − 1/d].

Proof. By the Frobenius Density Theorem the set of primes p for which the factorization of f(X) (mod p) contains exactly i linear factors has a Dirichlet density δ_{i}. Therefore, ∑_{i=0}^{d} δ_{i} = 1. By the Kronecker Density Theorem, we also have ∑_{i=0}^{d} iδ_{i} = 1. Hence,

r_{f} = δ_{0} = ∑_{i=1}^{d}(i − 1)δ_{i} ≥ (d − 1)δ_{d} ≥ \frac{d − 1}{♯G} ≥ \frac{d − 1}{d!},

where we wrote G for the Galois group of the splitting field of f(X). But if H is the subgroup of G that fixes some root of f(X), then, by the Frobenius Density Theorem, primes p that divide f(n) for some n have the Dirichlet density

\frac{♯ (∪_{x∈G}H^{x})}{♯G},

where for x ∈ G we wrote H^{x} = xHx^{−1}. Thus,

r_{f} = \frac{♯G − ♯ (∪_{x∈G}H^{x})}{♯G} ≤ \frac{♯G − ♯H}{♯G} = 1 − \frac{1}{d}.

But sets of primes thus arising from applying the Frobenius Density Theorem possess a (relative) asymptotic density equal to their Dirichlet density. □

We are now ready to prove Theorem 1.

Proof of Theorem 1. We may assume that a is not a k-th power, k ≥ 2. Indeed if a = b^{k}, then u_{n} = b^{g(n)} − 1, where g(X) is the integer valued polynomial kf(X). Furthermore, by replacing f(X) by 2f(X) if needed, we may assume that a is positive.

Let x be large. We put

y = \frac{1}{20} log log x.

Let q_{1} < ⋯ < q_{s} be all odd primes in R_{f}(y). It is clear that if p ∈ U_{f}(x), then ℓ_{a}(p) | f(n) for some positive integer n, therefore ℓ_{a}(p) cannot be divisible by any of the primes q_{i} for i = 1, …, s. Thus,

U_{f}(x) ⊂ {p ≤ x}\ (⋃_{i=1}^{s} A(x, q_{i})) ,

which shows, via the Principle of Inclusion and Exclusion, that

♯U_{f}(x) ≤ π(x) − ∑_{t=1}^{s}(−1)^{t−1} ∑_{i_{1}<···<i_{t}} ♯A(x, q_{i_{1}} … q_{i_{t}}).

Using estimate (1) and (2) with ε = 1/40, we get that

♯U_{f}(x) ≤ π(x) (1 + ∑_{t=1}^{s}(−1)^{t} ∑_{i_{1}<···<i_{t}} κ_{q_{i_{1}} ...q_{i_{t}}} + 2^{s}O (\frac{q_{1} … q_{s}}{(log x)^{1/10}} )) .

Having in mind the estimate ∑_{p≤y} log p = y(1 + o(1)), we note that

2^{s}q_{1} … q_{s} = exp ( s log 2 + ∑_{q∈R(y)} log q )

≤ exp (π(y) log 2 + ∫_{2^{−}}^{y} log t d♯R_{f}(t))
= exp (π(y) log 2 + r_{f} ∫_{2^{−}}^{y}(1 + o(1)) log t dπ(t))
= exp (π(y) log 2 + r_{f}(1 + o(1)) ∫_{2^{−}}^{y} log t dπ(t) + o(y))
= exp (o(y) + r_{f}y(1 + o(1)))
< exp(y) = (log x)^{1/20},

for large x since r_{f} < 1. Furthermore, we have

1 + ∑_{t=1}^{s}(−1)^{t} ∑_{i_{1}<···<i_{t}} κ_{q_{i_{1}} ...q_{i_{t}}} = 1 + ∑_{t=1}^{s}(−1)^{t} ∑_{i_{1}<···<i_{t}} ∏_{j=1}^{t} \frac{q_{i_{j}}}{q_{i_{j}}^{2} − 1}

= ∏_{i=1}^{s} (1 − \frac{q_{i}}{q_{i}^{2} − 1})

= α_{f} ∏_{q∈R_{f} (y)} (1 − \frac{1}{q}) ,

where

α_{f} = ∏_{q∈R_{f} (y)} (1 − \frac{1}{q})^{−1} (1 − \frac{q}{q^{2} − 1})

= ∏_{q∈R_{f} (y)} \frac{q(q^{2} − q − 1)}{(q − 1)(q^{2} − 1)}

= ∏_{q∈R_{f} (y)} \frac{q^{3} − q^{2} − q}{q^{3} − q^{2} − q + 1} < 1.

Hence,

1 + ∑_{t=1}^{s}(−1)^{t} ∑_{i_{1}<···<i_{t}} k_{q_{i_{1}} ...q_{i_{t}}} < ∏_{q∈R_{f} (y)} (1 − \frac{1}{q}) .

Since

∏_{q∈R_{f} (y)} (1 − \frac{1}{q}) < exp (− ∑_{q∈R_{f} (y)} \frac{1}{q})

= exp (− ∫_{2^{−}}^{y} \frac{1}{t} d♯R_{f}(t))

= exp (−r_{f}(1 + o(1)) ∫_{2^{−}}^{y} \frac{1}{t} dπ(t))

≤ exp (−r_{f}(1 + o(1)) log log y) = (log y)^{−r_{f} +o(1)}

= (log log log x)^{−r_{f} +o(1)},

we get that

♯U_{f}(x) ≤ π(x) (\frac{1}{(log log log x)^{r_{f} +o(1)}} + O (\frac{1}{(log x)^{1/20}} )) ,

which obviously implies the conclusion of the theorem. □

3. An application

Let (a_{n})_{n≥0} be an integral linear recurring sequence whose minimal characteristic polynomial g is a monic polynomial in ℤ[X] of degree 3 with integral roots that are distinct in absolute value. A prime p is a maximal divisor of (a_{n})_{n≥0} if it divides two consecutive terms a_{n}, a_{n+1} for some n. To such a g and such sequences (a_{n})_{n≥0} one associates a group structure of infinite rank and finite torsion in a natural way (see, for example, [3], p. 4 and 106-7). Based on experimental evidence, it seems that sequences not in the torsion subgroup have few maximal prime divisors (see [1], p. 44). Since there is a method to compute the positive Dirichlet density of such primes for ‘torsion’ sequences (see [1]), it would be interesting to assess the density for ‘nontorsion’ sequences. Is it always 0? We merely observe that for some nontorsion sequences such as the one of general term a_{n} = 2·3^{n}−3·2^{n}+1, Theorem 1 yields the answer. Indeed, assume a prime p > 3 is a prime dividing both a_{n} and a_{n+1} for some n. Then p divides a_{n+1} − a_{n} = 4 · 3^{n} − 3 · 2^{n}. Thus, 3^{n−1} ≡ 2^{n−2} (mod p). Similarly a_{n+1} −3a_{n} = 3·2^{n} −2 so that 3·2^{n−1} ≡ 1 (mod p). But raising this latter congruence to the power n − 1 and using 3^{n−1} ≡ 2^{n−2} (mod p), we get 2^{n^{2}−n−1} ≡ 1 (mod p). The polynomial X^{2} − X − 1 ∈ ℚ[X] being irreducible, the prime density of maximal divisors of (a_{n})_{n≥0} is 0. Note that if a prime p > 3 divides both b_{n} and b_{n+1}, where b_{n} = 3^{n+1} − 2^{n+2} + 6, then p divides both b_{n+1} − 2b_{n} and b_{n+1} − 3b_{n}, implying that

(3)  3^{n} ≡ 2 (mod p)  and  2^{n} ≡ 3 (mod p), for some n ≥ 0.

Here, we have 2^{n^{2}−1} ≡ 1 (mod p) and X^{2} − 1 is reducible so our result does not apply. However, Skałba [9] showed recently that primes satisfying (3) also have (relative) asymptotic density 0. Finally, note that the sequence of general term c_{n} = 3^{n} − 2^{n+1} − 1 is torsion of order 2 in the aforementioned group and that its associated density is 65/224 (see [1], Ch. 4). The problem of the relative density of maximal prime divisors of such ternary recurrent sequences is investigated in more detail in [2].

References

[1] Ballot, Christian. Density of prime divisors of linear recurrences. Mem. Amer. Math. Soc. 115 (1995), no. 551. MR1257079 (95i:11110), Zbl 0827.11006.

[2] Ballot, Christian; Luca, Florian. Common prime factors of a^{n} − b and c^{n} − d. Preprint, 2006.

[3] Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas. Recurrence sequences. Mathematical Surveys and Monographs, 104, Mathematical Society, Providence, RI, 2003. MR1990179 (2004c:11015), Zbl 1033.11006.

[4] Frobenius, G. Über Beziehungen zwischen den Primidealen eines algebraischen Körpers und den Substitutionen seiner Gruppe. S’ber. Akad. Wiss. Berlin (1896), 689–703. JFM 27.0091.04.

[5] Kronecker, L. Über die Irreductibilität von Gleichungen. Monatsb. König. Preuss. Akad. Wiss. Berlin (1880), 155–162. JFM 12.0065.02.

[6] Pappalardi, Francesco. Square free values of the order function. New York J. Math. 9 (2003), 331–344. MR2028173 (2004i:11116), Zbl 1066.11044.

[7] Pomerance, Carl; Shparlinski, Igor E. Smooth orders and cryptographic applications. Algorithmic number theory (Sydney, 2002), 338–348, Lect. Notes Comput. Sci. 2369, Springer, Berlin, 2002. MR2041095 (2005e:11117), Zbl 1058.11059.

[8] Odoni, R. W. K. A conjecture of Krishnamurthy on decimal periods and some allied problems. J. Number Theory 13 (1981), 303–319. MR0634201, Zbl 0471.10031.

[9] Skałba, M. Primes dividing both 2^{n} − 3 and 3^{n} − 2 are rare. Arch. Math. (Basel) 84 (2005), 485–495. MR2148488 (2006b:11114).

[10] Wiertelak, Kazimierz. On the density of some sets of primes p for which n | ord_{p}a. Funct. Approx. Comment. Math. 28 (2000), 237–241. MR1824009 (2003a:11120), Zbl 1009.11056.

Laboratoire de Mathématiques Nicolas Oresme, Université de Caen, BP 5186, 14032 Caen Cedex, France Christian.Ballot@math.unicaen.fr

Instituto de Matemáticas, Universidad Nacional Autonoma de México, C.P. 58089, Morelia, Michoacán, México fluca@matmor.unam.mx

This paper is available via http://nyjm.albany.edu/j/2006/12-3.html.