PRIME DIVISORS OF LUCAS SEQUENCES

Pieter Moree and Peter Stevenhagen

Abstract. The Lucas sequence associated to a real quadratic number field K is the integer sequence X_{K} = {ε^{n} + ε̄^{n}}_{n=0}^{∞}, with ε a fundamental unit in the ring of integers of K for which the trace ε + ε̄ is positive. In this note, we determine for all real quadratic fields K the natural density of the set of prime numbers p that divide some term of the sequence X_{K}.

1. Introduction

Let d > 1 be a squarefree integer and K = Q(\sqrt{d}) the corresponding real quadratic field. We write ε = a + b\sqrt{d} for a fundamental unit in the ring of integers of K and define the Lucas sequence associated to K to be the integer sequence

X_{K} = {Tr_{K/Q}(ε^{n})}_{n=0}^{∞} = {ε^{n} + ε̄^{n}}_{n=0}^{∞}.

For odd n the sign of x_{n} depends on the choice of the sign of a. This is irrelevant for the divisibility properties we will be concerned with, but for uniqueness sake we take x_{1} = 2a > 0.

The Lucas sequence X_{K} satisfies the second order linear recurrence

x_{n} = 2ax_{n−1} − N_{K/Q}(ε)x_{n−2}

for n ≥ 2. If we take for K the field Q(\sqrt{5}) generated by the golden ratio, we obtain the very classical example of the Lucas sequence with the familiar ‘Fibonacci recursion’ x_{n} = x_{n−1} + x_{n} and initial values x_{0} = 2 and x_{1} = 1.

In this note, we show that the set of prime numbers p that divide some term of the sequence X_{K} has a natural density δ_{K} and determine it for each K. More precisely, we compute the density δ_{K}^{+} of the primes that split completely in K and divide some term of X_{K} and the density δ_{K}^{−} of the primes that are inert in K and divide some term of X_{K}. The arguments for both kinds of primes are somewhat different, and so are the associated densities. It turns out that the determination of δ_{K}^{−} is the more difficult part, unless we are in the ‘easy case’ in which the norm N_{K/Q}(ε) equals −1, when it is trivially determined. Clearly, one has δ_{K} = δ_{K}^{+} +δ_{K}^{−}.

The method in this note extends to sequences {Tr_{K/Q}(α^{n})}_{n=0}^{∞} = {α^{n} +ᾱ^{n}}_{n=0}^{∞}, where α is any algebraic integer in a quadratic field K. Although it is a bit cumbersome to express the density as an explicit rational number in terms of α, this yields of proof of what is called a ‘main conjecture’ in [5, p. 362]. For more details, we refer to the treatment of general second order ‘torsion sequences’ in [4].

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 11R45; Secondary 11B39.

Key words and phrases. Lucas sequence, Chebotarev density theorem.

version April 20, 1997

Theorem. Let K = Q(\sqrt{d}) and a = \frac{1}{2}Tr_{K/Q}(ε) > 0 be as above. Then the natural densities δ_{K}^{+} and δ_{K}^{−} for the sets of prime divisors of the Lucas sequence associated to K exist. For N_{K/Q}(ε) = −1 the densities are as follows.

d = 2 d > 2
δ_{K}^{+} 11/24 5/12
δ_{K}^{−}  1/4  1/4
δ_{K} 17/24  2/3

For N_{K/Q}(ε) = 1 the densities depend in the following way on whether the integers a + 1 and a − 1 are squares or not.

a − 1 = □ a + 1 = □ a ± 1 ≠ □
δ_{K}^{+}  5/24  5/24  1/6
δ_{K}^{−}  1/8  5/24  1/6
δ_{K}  1/3  5/12  1/3

The main ingredient of the proof is the Chebotarev density theorem, and the basic idea of the method goes back to Hasse [1]. Lagarias [2] was the first to use this idea in a quadratic setting, for the classical Lucas sequence mentioned above, which falls in the category N_{K/Q}(ε) = −1. A generalization to other instances of units of norm −1 is given in [3].

2. Proof of the theorem.

Let K = Q(\sqrt{d}) and ε = a + b\sqrt{d} be as before, and write O for the ring of integers of K. If p is a prime that is unramified in K/Q, then the kernel of the norm map κ_{p} = ker[N : (O/pO)^{∗} → F_{p}^{∗}] is a cyclic group of order p − (\frac{d}{p}). We set

(2.1)  q = q_{K} = ε/ε̄ = \{ \begin{matrix}−ε^{2} & if N_{K/Q}(ε) = −1; \\ ε^{2} & if N_{K/Q}(ε) = 1. \end{matrix}

Let p ∤ 2d be a prime number. Looking at the explicit form of the n-th term x_{n} = ε^{n} +ε̄^{n} of X_{K}, we find that p divides x_{n} if and only if we have q^{n} = −1 ∈ (O/pO)^{∗}. As q lies in the cyclic subgroup κ_{p} ⊂ (O/pO)^{∗} and −1 is the unique element of order 2 in that group, we find the basic characterization

p divides some term of X_{K} ⟺ the order of q ∈ (O/pO)^{∗} is even.

The key idea in determining the densities δ_{K}^{+} and δ_{K}^{−} is that one can describe the parity of the order of q ∈ (O/pO)^{∗} in terms of the splitting behavior of p in some infinite algebraic extension of Q. We start with the easier case of the rational primes that split in K.

Split case. Let S^{+} be the set of odd primes p that split in K, and D^{+} ⊂ S^{+} the set of primes in S^{+} that divide some term of X_{K}.

For k ∈ Z_{≥1}, we let S_{k}^{+} ⊂ S^{+} be the set of primes p ∈ S^{+} for which p − 1 has exactly k = ord_{2}(p − 1) factors 2. The set S_{k}^{+} consists of the primes that split completely in the field K(ζ_{2^{k}}) obtained by adjoining to K a primitive 2^{k}-th root of unity, but not in the field K(ζ_{2^{k+1}}) obtained by adjoining to K a primitive 2^{k+1}-th root of unity. By the Chebotarev density theorem, the set S_{k}^{+} has a natural density inside the set of all primes. It equals δ(S_{k}^{+}) = [K(ζ_{2^{k}}) : Q]^{−1} − [K(ζ_{2^{k+1}}) : Q]^{−1}. Clearly, the sum of these densities for all k ≥ 1 is [K : Q]^{−1} = 1/2 = δ(S^{+}).

For p ∈ S_{k}^{+}, the group (O/pO)^{∗} is a product of two cyclic groups of order p − 1, and an element has odd order in (O/pO)^{∗} if and only if it is a 2^{k}-th power in (O/pO)^{∗}. As q ∈ (O/pO)^{∗} is a 2^{k}-th power if and only if p splits completely in the field K(ζ_{2^{k}}, \sqrt[2^{k}]{q}), we conclude that a prime p ∈ S_{k}^{+} does not divide a term of X_{K} if and only if it splits completely in K(ζ_{2^{k}}, \sqrt[2^{k}]{q}), but not in K(ζ_{2^{k+1}}, \sqrt[2^{k}]{q}). By the Chebotarev density theorem, the subset of such primes in S_{k}^{+} has natural density [K(ζ_{2^{k}}, \sqrt[2^{k}]{q}) : Q]^{−1} − [K(ζ_{2^{k+1}}, \sqrt[2^{k}]{q}) : Q]^{−1}. The complement D_{k}^{+} = D^{+} ∩ S_{k}^{+} of this set in S_{k}^{+} has a density as well, and we find that both D^{+} = ⋃_{k≥1} D_{k}^{+} and its complement S^{+} \ D^{+} = ⋃_{k≥1}(S_{k}^{+} \ D_{k}^{+}) in S^{+} are countable disjoint unions of sets of primes having a natural density. It follows that D^{+} has lower density ∑_{k≥1} δ(D_{k}^{+}), and that S^{+} \ D^{+} has lower density ∑_{k≥1} δ(S_{k}^{+} \ D_{k}^{+}). These lower densities add up to δ(S^{+}), so they are in fact densities. We conclude that D^{+} has a natural density δ_{K}^{+} which satisfies

(2.2)  \frac{1}{2} − δ_{K}^{+} = ∑_{k≥1}(\frac{1}{[K(ζ_{2^{k}}, \sqrt[2^{k}]{q}) : Q]} − \frac{1}{[K(ζ_{2^{k+1}}, \sqrt[2^{k}]{q}) : Q]}).

Equation (2.2) reduces the computation of δ_{K}^{+} to a computation of field degrees in the infinite extension K(ζ_{2^{∞}}, \sqrt[2^{∞}]{q}) of Q. To ease notation we write

F_{k} = K(ζ_{2^{k+1}}, \sqrt[2^{k}]{q}).

Then the k-th term of the right hand side of (2.2) equals [F_{k} : Q]^{−1} if ζ_{2^{k+1}} generates a quadratic extension of K(ζ_{2^{k}}, \sqrt[2^{k}]{q}), and 0 otherwise.

Suppose first that we have N_{K/Q}(ε) = −1, and consequently q = −ε^{2} in (2.1). Then q is a square in K(ζ_{4}), and also in the field M = K(ζ_{2^{∞}}) obtained by adjoining all 2-power roots of unity to K. It is not a fourth power in M as M is abelian over Q and M(\sqrt[4]{q}) = M(\sqrt{ε}) has a quartic subfield K(\sqrt{ε}) that is not normal over Q. By Kummer theory, it follows that \sqrt[2^{k}]{q} generates a cyclic extension of degree 2^{k−1} of K(ζ_{2^{k}}) for every k ≥ 2. Our normality argument shows that this extension is linearly disjoint over K(ζ_{2^{k}}) from K(ζ_{2^{k+1}}) .

For k = 1, we have a quadratic extension K(\sqrt{q}) = K(ζ_{4}), which coincides with the extension generated by ζ_{2^{k+1}} = ζ_{4}. This shows that the term for k = 1 always vanishes in (2.2).

If K is not the real quadratic subfield Q(\sqrt{2}) of Q(ζ_{2^{∞}}), then ζ_{2^{k+1}} generates a quadratic extension of K(ζ_{2^{k}}) for all k ≥ 2, and F_{k} has degree 2 · 2^{k} · 2^{k−1} = 4^{k} for these k. We find \frac{1}{2} − δ_{K}^{+} = ∑_{k≥2} 4^{−k} = \frac{1}{12} and δ_{K}^{+} = \frac{5}{12}.

For K = Q(\sqrt{2}) the degree of F_{k} is only 2^{k} · 2^{k−1} = 2^{2k−1} for k ≥ 3. Moreover, the term for k = 2 in (2.2) vanishes since K(ζ_{4}) = Q(ζ_{8}) now contains ζ_{2^{k+1}} = ζ_{8}. We find \frac{1}{2} − δ_{K}^{+} = ∑_{k≥3} 2^{1−2k} = \frac{1}{24} and δ_{K}^{+} = \frac{11}{24}.

The diagrams below indicate the field degrees in the two situations for k ≥ 2 and k ≥ 3, respectively,

F_{k}  F_{k}
[figure: 2; 2]
K(ζ_{2^{k+1}})  K(ζ_{2^{k}} , \sqrt[2k]{q})  K(ζ_{2^{k+1}})  K(ζ_{2^{k}} , \sqrt[2k]{q})
[figure: 2^{k−1}; 2^{k−1}]
K(ζ_{2^{k}})  K(ζ_{2^{k}})
2^{k−2}  2^{k−3}
K(ζ_{4}) = K(\sqrt{q})  K(ζ_{8}) = K(\sqrt{q})
2  2
K ≠ Q(\sqrt{2})  K = Q(\sqrt{2})

Suppose next that we have N_{K/Q}(ε) = 1, and so in particular K ≠ Q(\sqrt{2}). The analysis is similar to the previous case, but we now have q = ε^{2}, so q is a square in K. As the field K(\sqrt[4]{ε}) is non-normal of degree 8, we see that q = ε^{2} is a square in M = K(ζ_{2^{∞}}), but not an eighth power. We have two cases.

Suppose q is not a fourth power in M. Then \sqrt[2^{k}]{q} generates a cyclic extension of degree 2^{k−1} of K(ζ_{2^{k}}) for every k ≥ 1, and this extension is linearly disjoint from the extension of K(ζ_{2^{k}}) generated by ζ_{2^{k+1}}. This is similar to the case K ≠ Q(\sqrt{2}) above, the only difference being that we now also have a non-zero term for k = 1 in (2.2). We find \frac{1}{2} − δ_{K}^{+} = ∑_{k≥1} 4^{−k} = \frac{1}{3} and δ_{K}^{+} = \frac{1}{6}.

Suppose that q is a fourth power in M. Then K(\sqrt{ε}) is a subfield of M. Besides K, the quadratic subfields of K(\sqrt{ε}) are the two fields Q(\sqrt{ε}±1/\sqrt{ε}), and one of those two is contained in Q(ζ_{2^{∞}}). ¿From N_{K/Q}(ε) = 1 we deduce

(2.3)  (\sqrt{ε} ± 1/\sqrt{ε})^{2} = Tr_{K/Q}(ε) ± 2 = 2(a ± 1),

so this happens exactly when one of the integers a ± 1 is a square. The fields K(ζ_{4}, \sqrt[4]{q}) = K(ζ_{4}, \sqrt{ε}) and K(ζ_{8}) now coincide, and \sqrt[2^{k}]{q} generates, for all k ≥ 3, a cyclic extension of degree 2^{k−2} of K(ζ_{2^{k}}) that is linearly disjoint over K(ζ_{2^{k}}) from K(ζ_{2^{k+1}}). As in the case K = Q(\sqrt{2}) above, the degree of F_{k} is now only 2^{k} · 2^{k−1} = 2^{2k−1} for k ≥ 3. The term for k = 2 vanishes, but for k = 1 we do have a contribution \frac{1}{4}. We find \frac{1}{2} − δ_{K}^{+} = \frac{1}{4} + ∑_{k≥3} 2^{1−2k} = \frac{7}{24} and δ_{K}^{+} = \frac{5}{24} if a + 1 or a − 1 is a square. This shows that the values of δ_{K}^{+} are as asserted.

Inert case. Let p be a prime that is inert in K/Q. Then O/pO is a field of p^{2} elements, and the norm map N : O/pO → F_{p} raises all elements to the power p+1.

Suppose first that we are in the case N_{K/Q}(ε) = −1. Then we have q = −ε^{2} in (2.1) and ε^{p+1} = −1 ∈ (O/pO)^{∗}. For p ≡ 1 mod 4 we obtain q^{(p+1)/2} = −ε^{p+1} = 1 ∈ (O/pO)^{∗}, which shows that the order of q in (O/pO)^{∗} is odd. For p ≡ 3 mod 4 we obtain q^{(p+1)/2} = ε^{p+1} = −1 ∈ (O/pO)^{∗}, which shows that the order of q in (O/pO)^{∗} is even. We find that δ_{K}^{−} is the density of the primes p ≡ 3 mod 4 that are inert in K/Q and equals δ_{K}^{−} = 1/4.

¿From now on we suppose N_{K/Q}(ε) = 1. In particular, this implies K ≠ Q(\sqrt{2}). We have q = ε^{2}, and consequently q^{(p+1)/2} = ε^{p+1} = 1 ∈ (O/pO)^{∗} for all inert odd primes p. This shows that for all inert primes p ≡ 1 mod 4, the order of q is again odd and p does not divide a term of X_{K}. For the inert primes p ≡ 3 mod 4 we use an approach that is similar to that in the split case.

Let S^{−} be the set of odd primes p that are inert in K/Q, and D^{−} ⊂ S^{−} the set of primes in S^{−} that divide some term of X_{K}. For k ∈ Z_{≥2}, we let S_{k}^{−} ⊂ S^{−} be the set of primes p ∈ S^{−} for which p + 1 has exactly k = ord_{2}(p + 1) factors 2. This is a set with a natural density, and we want to compute the density of the subset D_{k}^{−} = D^{−} ∩ S_{k}^{−} by characterizing the primes p ∈ D_{k}^{−} in terms of splitting conditions on p in some finite Galois extension F_{k}/Q.

A prime p is in S_{k}^{−} if and only if its Frobenius substitution in the abelian group Gal(K(ζ_{2^{k+1}})/Q) is the unique element φ that is non-trivial on K and acts on the 2^{k+1}-th roots of unity as φ(ζ_{2^{k+1}}) = ζ_{2^{k+1}}^{−1+2^{k}}. As K(ζ_{2^{k+1}}) has degree 2^{k+1} over Q, this shows that S_{k}^{−} has natural density 2^{−k−1} for all k. We let B_{k} ⊂ K(ζ_{2^{k+1}}) be the subfield corresponding to the subgroup ⟨φ⟩ of Gal(K(ζ_{2^{k+1}})/Q). Note that K(ζ_{2^{k+1}}) = B_{k}(ε) is a quadratic extension of B_{k}.

If p is in S_{k}^{−}, the order p^{2} − 1 = (p − 1)(p + 1) of the cyclic group (O/pO)^{∗} has exactly k + 1 ≥ 3 factors 2, and q = ε^{2} ∈ (O/pO)^{∗} has odd order if and only if ε^{2} is a 2^{k+1}-th power in (O/pO)^{∗}. As −1 is a 2^{k}-th power in (O/pO)^{∗}, we conclude that p ∈ S_{k}^{−} does not divide any term of X_{K} if and only if ε is a 2^{k}-th power in (O/pO)^{∗}. This leads to a characterization of the primes p ∈ S_{k}^{−} outside D^{−} in terms of their splitting behavior in the field

F_{k} = K(ζ_{2^{k+1}}, \sqrt[2^{k}]{ε}) = B_{k}( \sqrt[2^{k}]{ε});

they are the primes p that split completely in B_{k} and have extensions in B_{k} that are inert in B_{k}(ε)/B_{k} and split in F_{k}/B_{k}(ε). This means that the Frobenius symbol of p in the non-abelian group Gal(F_{k}/Q), which is only determined up to conjugacy, is an element of order 2 in the normal subgroup Gal(F_{k}/B_{k}) that does not lie in the normal subgroup Gal(F_{k}/B_{k}(ε)). If n_{k} denotes the number of such elements in Gal(F_{k}/Q), the Chebotarev density theorem yields an inert analogue of (2.2):

(2.4)  \frac{1}{2} − δ_{K}^{−} = \frac{1}{4} + ∑_{k≥2} \frac{n_{k}}{[F_{k} : Q]} = \frac{1}{4} + ∑_{k≥2} 2^{−k} \frac{n_{k}}{[F_{k} : B_{k}]}.

This time we have to do slightly more than a degree computation, since we also need to know the structure of the group Gal(F_{k}/B_{k}).

Suppose first that neither a−1 nor a+1 is a square. Then the extensions K(\sqrt{ε}) and K(ζ_{2^{∞}}) are linearly disjoint over K, and F_{k}/B_{k}(ε) is a cyclic extension of degree 2^{k} generated by \sqrt[2^{k}]{ε}. We can extend the generator φ of Gal(B_{k}(ε)/B_{k}) to an element φ^{∗} ∈ Gal(F_{k}/B_{k}) of order 2 by setting φ^{∗}( \sqrt[2^{k}]{ε}) = 1/ \sqrt[2^{k}]{ε}. As φ^{∗} acts by inversion on both ⟨ε⟩ and ⟨ζ_{2^{k}}⟩, the Galois-equivariancy of the Kummer pairing

Gal(F_{k}/B_{k}(ζ_{2^{k+1}})) × ⟨ε⟩ ⟶ ⟨ζ_{2^{k}}⟩

shows that φ^{∗} commutes with all elements in Gal(F_{k}/B_{k}(ε)). We find

Gal(F_{k}/B_{k}) ≅ Gal(F_{k}/B_{k}(ε)) × ⟨φ^{∗}⟩ ≅ Z/2^{k}Z × Z/2Z.

As there are exactly two elements of order 2 in Gal(F_{k}/B_{k}) of the form (σ, φ^{∗}), this yields n_{k} = 2 in (2.4) for all k ≥ 2. We find \frac{1}{2} − δ_{K}^{−} = \frac{1}{4} + ∑_{k≥2} 2^{−k} · 2 · 2^{−k−1} = \frac{1}{3}

and δ_{K}^{−} = \frac{1}{6}. B_{k}( \sqrt[2k]{ε})= F_{k}

[figure: ⟨φ^{∗}⟩]
B_{k}(\sqrt{ε})  B_{k}( \sqrt[2k]{ε} + 1/ \sqrt[2k]{ε})
[figure: 2; 2^{k−1}]
K(ζ_{2^{k+1}}) =B_{k}(ε) B_{k}(\sqrt{ε} − \frac{1}{\sqrt{ε}}) B_{k}(\sqrt{ε} + \frac{1}{\sqrt{ε}})
[figure: ⟨φ⟩; 2]
B_{k}

Suppose now that either a + 1 or a − 1 is a square. Then the extension F_{k}/B_{k} in the diagram above collapses to an extension of degree 2^{k} for all k ≥ 2. For k ≥ 3, we have \sqrt{2} ∈ B_{k} and (2.3) shows that B_{k} contains \sqrt{ε} + 1/\sqrt{ε} if a + 1 is a square and \sqrt{ε} − 1/\sqrt{ε} if a − 1 is a square. In the first case we have an isomorphism

Gal(F_{k}/B_{k}) ≅ Gal(B_{k}(\sqrt{ε})/B_{k}) × ⟨φ^{∗}⟩ ≅ Z/2^{k−1}Z × Z/2Z

and n_{k} = 2 as before. In the other case, F_{k}/B_{k} is a cyclic extension of degree 2^{k} with quadratic subextension B_{k}(ε) = B_{k}(\sqrt{ε}). Any extension of φ ∈ Gal(B_{k}(ε)/B_{k}) to F_{k} is then a generator of Gal(F_{k}/B_{k}), and we have n_{k} = 0.

For k = 2, any of the elements \sqrt{2} and \sqrt{ε} ± 1/\sqrt{ε} generates the quadratic extension B_{2}(\sqrt{ε}) = B_{2}(\sqrt{2}) of B_{2}. The extension B_{2} ⊂ B_{2}(\sqrt[4]{ε}) = F_{2} is of degree 4 and has a quadratic subextension generated by \sqrt{ε} = \sqrt{(a + 1)/2} + \sqrt{(a − 1)/2}. If a + 1 is a square, then \sqrt{ε} has norm −1 in B_{k} and F_{2}/B_{2} is a cyclic extension. If a − 1 is a square, then \sqrt{ε} has norm 1 in B_{k} and F_{2}/B_{2} is a V_{4}-extension. The corresponding values of n_{2} are n_{2} = 0 and n_{2} = 2.

For a + 1 a square we find \frac{1}{2} − δ_{K}^{−} = \frac{1}{4} + 0 + ∑_{k≥3} 2^{−k} · 2 · 2^{−k} = \frac{7}{24} and δ_{K}^{−} = \frac{5}{24}. For a − 1 a square we find a finite sum \frac{1}{2} − δ_{K}^{−} = \frac{1}{4} + \frac{1}{8} and δ_{K}^{−} = \frac{1}{8}. This finishes the proof of the theorem.

References

1. H. Hasse, Über die Dichte der Primzahlen p, für die eine vorgegebene rationale Zahl a ≠ 0 von durch eine vorgegebene Primzahl l ≠ 2 teilbarer bzw. unteilbarer Ordnung mod p ist, Math. Ann. 162 (1965), 74–76.

2. J. C. Lagarias, The set of primes dividing the Lucas numbers has density 2/3, Pacific J. Math. 118 (1985), 449–461; Errata: Pacific J. Math. 162 (1994), 393–397.

3. P. Moree, On the prime density of Lucas sequences, J. Théor. Nombres Bordeaux 8 (1996), 449–459.

4. P. Moree and P. Stevenhagen, Prime densities for linear recurrences (in preparation).

5. P. Ribenboim, The new book of prime number records, Springer, New York, 1995.

Max-Planck-Institut für Mathematik, Gottfried-Claren-Straße 26, 53225 Bonn, Germany

   E-mail address: moree@mpim.bonn.mpg.de

Faculteit WINS, Universiteit van Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands

   E-mail address: psh@wins.uva.nl