The Terms in Lucas Sequences Divisible by Their Indices

Chris Smyth

School of Mathematics and Maxwell Institute for Mathematical Sciences

University of Edinburgh James Clerk Maxwell Building King’s Buildings Mayfield Road Edinburgh EH9 3JZ United Kingdom

                   c.smyth@ed.ac.uk

Abstract

For Lucas sequences of the first kind (u_{n})_{n≥0} and second kind (v_{n})_{n≥0} defined as usual by u_{n} = (α^{n} − β^{n})/(α − β), v_{n} = α^{n} + β^{n}, where α and β are either integers or conjugate quadratic integers, we describe the sets {n ∈ ℕ : n divides u_{n}} and {n ∈ ℕ : n divides v_{n}}. Building on earlier work, particularly that of Somer, we show that the numbers in these sets can be written as a product of a so-called basic number, which can only be 1, 6 or 12, and particular primes, which are described explicitly. Some properties of the set of all primes that arise in this way is also given, for each kind of sequence.

1 Introduction

Given integers P and Q, let α and β be the roots of the equation

x^{2} − P x + Q = 0.

Then the well-known Lucas sequence of the first kind (or generalised Fibonacci sequence) (u_{n})_{n≥0} is given by u_{0} = 0, u_{1} = 1 and u_{n+2} = P u_{n+1} − Qu_{n} for n ≥ 0, or explicitly by Binet’s formula

u_{n} = \frac{α^{n} − β^{n}}{α − β}

when Δ = (α − β)^{2} = P^{2} − 4Q ≠ 0, and u_{n} = nα^{n−1} when Δ = 0. In this latter case α is an integer, and so n divides u_{n} for all n ≥ 1. In Theorem 1 below we describe, for all pairs (P, Q), the set S = S(P, Q) of all n ≥ 1 for which n divides u_{n}.

Corresponding to Theorem 1 we have a similar result (Theorem 12 below) for the Lucas sequence of the second kind (v_{n})_{n≥0}, given by v_{0} = 2, v_{1} = P and v_{n+2} = P v_{n+1} − Qv_{n} for n ≥ 0, or explicitly by the formula

v_{n} = α^{n} + β^{n},

finding the set T = T (P, Q) of all n ≥ 1 for which n divides v_{n}. The results for the set T are given in Section 4.

For n ∈ S, define P_{S,n} to be the set of primes p such that np ∈ S. We call an element n of S (first kind) basic if there is no prime p such that n/p is in S. We shall see that, for given P, Q, there are at most two basic elements of S. It turns out that all elements of S are generated from basic elements using primes from these sets.

Theorem 1. (a) For n ∈ S, the set P_{S,n} is the set of primes dividing u_{n}Δ.

(b) Every element of S can be written in the form bp_{1} … p_{r} for some r ≥ 0, where b ∈ S is basic and, for i = 1, …, r, the numbers bp_{1} … p_{i−1} are also in S, and p_{i} is in P_{S,bp_{1}...p_{i−1}}.

(c) The (first kind) basic elements of S are

• 1 and 6 if P ≡ 3 (mod 6), Q ≡ ±1 (mod 6);

• 1 and 12 if P ≡ ±1 (mod 6), Q ≡ −1 (mod 6);

• 1 only, otherwise.

Note that the primes in part (b) need not be distinct.

Somer [20, Theorem 4] has many results in the direction of this theorem. In particular, he already noted the importance of 6 and 12 for this problem. Walsh [23, unpublished] gave an equivalent categorization of S(1, −1) (the Fibonacci numbers case), a case where 1 and 12 are the basic elements of S(1, −1).

Note that if α and β are integers, then at least one of P, Q is even, so that 1 is the only basic element in this case. In this case, too, it is known (see André-Jeannin [2]) that S = {n : n | α^{n} − β^{n}}. (His result is stated assuming that gcd(n, αβ) = 1, and his proof given for n square-free). This follows straight from Proposition 11 below. Further, for α and β integers with gcd(α, β) = 1, Győry [10] proved that, for a fixed integer r, the number of elements of S with r prime factors was finite, and described how to find them. See also [11] for the more general problem of the divisibility of α^{n} − β^{n} (α, β integers) by powers of n.

Now let P_{S} be the set of primes p that divide some n in S. It is easy to see that P_{S} = ∪_{n∈S}P_{S,n}. It is interesting to compare P_{S,n} and P_{S,np} for n and np in S. Write u_{n} = u_{n}(α, β) to show the dependence of u_{n} on α and β, and denote u_{n}(α^{k}, β^{k}) by u_{n}^{(k)}. Then since

u_{kn} = u_{k}^{(n)}u_{n},  (1)

we have u_{n} | u_{np}, so that P_{S,n} ⊂ P_{S,np} by Theorem 1(b). Thus when we multiply n ∈ S by a succession of primes according to Theorem 1(b) to stay within S, the associated set P_{S,n} does not lose any primes. Hence we obtain the following consequence of Theorem 1(a).

Corollary 2. If n ∈ S and all prime factors of m divide u_{n}Δ, then nm ∈ S.

This is a strengthening of the known result (see e.g., [20, Theorem 5(i)]) that if n ∈ S and all prime factors of m divide nΔ, then nm ∈ S. In particular (n = 1) Δ ∈ S and, for n ∈ S, both u_{n} = n · (u_{n}/n) ∈ S and u_{n}Δ ∈ S.

In Section 7 we give the conditions on P and Q that make S, P_{S}, T or P_{T} finite. In Section 8 we compare P_{S} with the set P_{1st} of primes that divide some u_{n} and the set P_{T} with the set P_{2nd} of primes that divide some v_{n} with n ≥ 1. In Section 9 we briefly discuss divisibility properties of the sequences S and T. These properties are useful for generating the sequences efficiently.

It is of interest to estimate {n ∈ S : n ≤ x} and {n ∈ T : n ≤ x}. It is planned to do this in a forthcoming paper of Shparlinski and the author. For P_{S} infinite (and not the set P of all primes!) it would also be of interest to estimate the relative density of P_{S} in P. But this seems to be a more difficult problem (as does the corresponding problem for T).

A basic reference for Lucas numbers is the monograph of Williams [24]. See also Dickson [8, Chapter 17], and Ribenboim [17]. For a more general reference on recurrence sequences see the book [9] by Everest, van der Poorten, Shparlinski, and Ward.

2 Preliminary results for S.

While Theorem 1(b) allows us to multiply n ∈ S by the primes in P_{S,n} to stay within S, a vital ingredient in proving Theorem 1(c) is to be able to do the opposite: to divide n ∈ S by a prime and stay within S. This is provided by the following significant result, due to Somer, generalising special cases due to Jarden [13, Theorem E], Hoggatt and Bergum [12] and Walsh [23] for the Fibonacci sequence (i.e., P = 1, Q = −1) and André-Jeannin [2] for gcd(P, Q) = 1.

Theorem 3 (Somer [20, Theorem 5(iv)]). Let n ∈ S, n > 1, with p_{max} its largest prime factor. Then, except in the case that P is odd and n is of the form 2^{ℓ} · 3 for some ℓ ≥ 1, we have n/p_{max} ∈ S.

We produce a variant of this result to cover all but two of the exceptional cases, as follows.

Proposition 4. If P is odd and n = 2^{ℓ} · 3 ∈ S, where ℓ ≥ 3, then n/2 ∈ S.

The idea of the proof of Theorem 3 is roughly (i.e., ignoring some details) as follows. Let n have prime factorization n = ∏_{p} p^{k_{p}}, with ω(n), the rank of appearance of n, being the least integer k such that n | u_{k}. Then n | u_{n} is equivalent to ω(n) | n. Since ω(n) = lcm_{p} ω (p^{k_{p}}), and every ω (p^{k_{p}}) is of the form p^{k′_{p}}ℓ_{p}, where k′_{p} < k_{p} and ℓ_{p} | (p^{2} − 1), it follows that n | u_{n} is equivalent to

lcm_{p|n} (p^{k′_{p}}ℓ_{p}) | n = ∏_{p|n} p^{k_{p}}.  (2)

But since for p > 2 all prime factors of p^{2} − 1 are less than p, and 2^{2} − 1 = 3, if equation (2) holds, it will still hold with n replaced by n/p_{max} when p_{max} > 3 or p_{max} = 3 and (n odd or 2 | n with ℓ_{2} = 1). When p_{max} = 3 and 2 | n with ℓ_{2} = 3, (2) will still hold with n replaced by n/3 as long as n/3 is divisible by 3.

For the proof of Theorem 1, we first need the following, which dates back to Lucas [15, p. 295] and Carmichael [7, Lemma II]. It is the special case n = 1 of Theorem 1(a).

Lemma 5. For any prime p, p divides u_{p} if and only if p divides Δ.

Proof. Now u_{2} = P and Δ = P^{2} − 4Q ≡ u_{2} (mod 2), so the result is true for p = 2. The result is trivial for Δ = 0. Now for Δ ≠ 0 and p ≥ 3,

Δ^{(p−1)/2} = \frac{(α − β)^{p}}{(α − β)}

= u_{p} + ∑_{j=1}^{p−1} \binom{p}{j}α^{p−j}(−β)^{j}/(α − β)

= u_{p} + ∑_{j=1}^{(p−1)/2} \binom{p}{j}(−1)^{j}Q^{j}u_{p−2j}

≡ u_{p} (mod p),

giving the result.

We have the following.

A prime is called irregular if it divides Q but not P. Clearly p ∤ Δ for p irregular. A prime that is not irregular is called regular.

Lemma 6 (Lucas [15, pp. 295–297], Carmichael [7, Theorem XII], Somer [20, Proposition 1(viii)], Williams [24, pp. 83–84] ). If p is an odd prime with p ∤ Q, p ∤ Δ, then p | u_{p−ε}, where ε is the Legendre symbol (\frac{Δ}{p}). On the other hand, if p is irregular then it does not divide any u_{n}, n ≥ 1.

The following result follows easily from Lemmas 5 and 6.

Corollary 7. The set P_{1st} of primes that divide some u_{n}, n ≥ 1 consists precisely of the regular primes.

Lemma 8 (Somer [20, Theorem 5(ii)]). If m, n ∈ S then lcm(m, n) ∈ S.

Proof. Put ℓ = lcm(m, n). From (1) we have u_{n} | u_{ℓ}, u_{m} | u_{ℓ}, so n | u_{n}, m | u_{m} and hence ℓ | u_{ℓ}.

Lemma 9. We have

(i) If P is odd and 2^{ℓ} | u_{12}, where ℓ ≥ 1, then 2^{ℓ−1} | u_{6};

(ii) If 3 | u_{8k} then 3 | u_{4k}.

Proof. Using the notation

P^{(k)} = P (α^{k}, β^{k}) = α^{k} + β^{k} = v_{k}, Q^{(k)} = Q(α^{k}, β^{k}) = Q^{k},

we have P^{(2)} = P^{2} − 2Q and

P^{(4)} = (P^{2} − 2Q)^{2} − 2Q^{2} = P^{4} − 4P^{2}Q + 2Q^{2}.  (3)

(i) Take P odd. Then

P^{(2)} ≡ \begin{cases}1 (mod 4), if Q even; \\ −1 (mod 4), if Q odd, \end{cases}

and so P^{(4)} ≡ P^{(2)} (mod 4) and

v_{6} = P^{(2)}(P^{(4)} − Q^{2}) ≡ \begin{cases}1 (mod 4), if Q even; \\ 2 (mod 4), if Q odd. \end{cases}

Since u_{12} = u_{6}v_{6} by (1) and 2 ∤ u_{12} for Q even, we get the result.

(ii) Since u_{4k} = u_{k}^{(4)}u_{4}, it is enough to prove that if 3 | u_{2k}^{(4)} and 3 ∤ u_{4} then 3 | u_{k}^{(4)}. Now, working modulo 3, P^{(4)} ≡ P^{2}(1 − Q) − Q^{2}, using (3) and P^{4} ≡ P^{2}. Thus

\binom{P^{(4)}}{Q^{(4)}} = \begin{cases}\binom{0}{0}, if P ≡ Q ≡ 0; \\ \binom{1}{0}, if P ≡ ±1, Q ≡ 0; \\ \binom{1}{1}, if P ≡ ±1, Q ≡ −1; \\ \binom{−1}{1}, otherwise. \end{cases}

The result holds in the first case because u_{4} ≡ 0, and in the second case because u_{n}^{(4)} ≡ 1 for all n ≥ 1. In the other two cases, u_{n}^{(4)} ≡ 0 precisely when 3 | n, so the result holds also in these cases.

Proposition 10. If P is odd and 2^{ℓ} · 3 ∈ S, where ℓ ≥ 3, then 2^{ℓ−1} · 3 ∈ S. In particular, then 12 ∈ S.

Proof. Take P odd. Then P^{(2)} = P^{2} − 2Q is also odd, and hence so are all P^{(2^{ℓ})} = v_{2^{ℓ}} for ℓ ≥ 0. Then for ℓ ≥ 3, using (1) and u_{2k} = u_{k}v_{k} we have

u_{2^{ℓ}·3} = u_{12}^{(2^{ℓ−2})}u_{2^{ℓ−2}} = u_{12}^{(2^{ℓ−2})}v_{2^{ℓ−3}}v_{2^{ℓ−4}} … v_{2}v_{1}.

So if 2^{ℓ} | u_{2^{ℓ}·3} then 2^{ℓ} | u_{12}^{(2^{ℓ−2})} so, by Lemma 9(i), 2^{ℓ−1} | u_{6}^{(2^{ℓ−2})}. Hence

2^{ℓ−1} | u_{6}^{(2^{ℓ−2})}u_{2^{ℓ−2}} = u_{2^{ℓ−1}·3}.

Also, if 3 | u_{2^{ℓ}·3} where ℓ ≥ 3 then 3 | u_{2^{ℓ−1}·3}, by Lemma 9(ii). Thus we have proved that if ℓ ≥ 3 and 2^{ℓ} · 3 ∈ S then 2^{ℓ−1} · 3 ∈ S. Then 12 ∈ S follows.

Proposition 11. For any positive integer n and distinct integers a, b,

n | a^{n} − b^{n} ⟹ n | \frac{a^{n} − b^{n}}{a − b} .

Proof. For any prime p, suppose that p^{ℓ}∥a − b and p^{r}∥n. It is clearly enough to prove that p^{r+ℓ} | a^{n} − b^{n} whenever ℓ > 0. Put a = b + λp^{ℓ}. Then

a^{n} − b^{n} = ∑_{k=1}^{n} \binom{n}{k}λ^{k}p^{ℓk}b^{n−k}

= ∑_{k=1}^{n} \frac{n}{k}\binom{n − 1}{k − 1}λ^{k}p^{ℓk}b^{n−k}

≡ 0 (mod p^{L}),

where

L ≥ r + min_{k=1}^{n}(ℓk − ⌊log_{p} k⌋)

≥ r + ℓ + min_{k=1}^{n}(ℓ(k − 1) − log_{2} k)

≥ r + ℓ + min_{k=1}^{n}((k − 1) − log_{2} k)

= r + ℓ.

3 Proof of Theorem 1.

To prove part (a), take n ∈ S and p prime. First note that, from (1), u_{np} = u_{p}^{(n)}u_{n}. Now suppose that np | u_{np}. Then either p | u_{n}, or, by Lemma 5, we have p | Δ^{(n)}, where Δ^{(n)} = (α^{n} − β^{n})^{2} = u_{n}^{2}Δ. Hence p | u_{n}Δ.

Conversely, suppose p | u_{n}Δ. Then p | Δ^{(n)}, so that, by Lemma 5, p | u_{p}^{(n)}, giving pn | u_{p}^{(n)}u_{n} = u_{np}.

To prove (b), take n ∈ S, n ≠ 1, 6 or 12. If 3 ∈ S then 3/3 = 1 ∈ S. Otherwise, by Theorem 3 and Proposition 10, we have n/p ∈ S for some prime factor p of n. Thus we obtain a sequence n, n/p, (n/p)/p′, … of elements of S, which stops only at 1, 6 or 12. But clearly 6 and 12 cannot both be basic, so the process will stop at either 1 (always basic!) or at most one of 6 and 12. This shows that this sequence, written backwards, must be of the form b, bp_{1}, bp_{1}p_{2}, …, bp_{1} … p_{r}, say, as required. By (a), we know that p_{i} is in P_{S,bp_{1}...p_{i−1}}.

To prove (c), we just need to find for which P, Q the numbers 6 or 12 are basic.

The case 6 ∈ S, 3 ∉ S, 2 ∉ S. Since u_{2} = P, we know that 2 ∈ S iff P is even. Hence P is odd. Also

u_{6} = u_{3}v_{3} = (P^{2} − Q)(P^{2} − 3Q)P.  (4)

As 6 | u_{6} and 3 ∤ u_{3} = P^{2} − Q, we have 3 | P, and so Q ≡ ±1 (mod 3). Also Q must be odd, so P ≡ 3 (mod 6) and Q ≡ ±1 (mod 6).

The case 12 ∈ S, 6 ∉ S, 4 ∉ S. Since 2 ∉ S by Corollary 2, we have P odd, as above. Now u_{12} = u_{6}v_{6} and

v_{6} = v_{3}^{(2)} = (P^{2} − 2Q)((P^{2} − 2Q)^{2} − 3Q^{2}).  (5)

If Q were even, then by (4) and (5) u_{6}, v_{6}, and u_{12} would all be odd. So Q is odd. As u_{6} is then even, 3 ∤ u_{6}, and we have P ≡ ±1 (mod 3) and Q ≡ 0 or − 1 (mod 3). As 3 | u_{12}, also 3 | v_{6} ≡ (P^{2} − 2Q)^{3} (mod 3), giving Q ≡ −1 (mod 3). Hence P ≡ ±1 (mod 6) and Q ≡ −1 (mod 6).

The converse for both of these cases is easily checked.

4 The set T

The results for the set T = {n ∈ ℕ : n | v_{n}} differ slightly from those for S. Essentially, this is because of difficulties at the prime 2: v_{n} divides v_{np} for p odd, but not in general for p = 2. The main result is the following. For n ∈ T, define P_{T,n} to be the set of primes p such that np ∈ T. A prime is said to be special if it divides both P and Q. It is clear from applying the recurrence relation that all v_{n} for n ≥ 1 are divisible by gcd(P, Q), and so by all special primes. We say that an element n of T is (second kind) basic if there is no prime p such that n/p is in T.

Theorem 12. (a) For n ∈ T, the set P_{T,n} is the set of odd primes dividing v_{n}, with the possible inclusion of 2. Specifically, the prime 2 is in P_{T,n} if and only if n is a product of special primes and either

• P is even; or

• Q is odd and 3 | n.

(b) Every element of T can be written in the form bp_{1} … p_{r} for some r ≥ 0, where b ∈ T is (second kind) basic and, for i = 1, …, r, the numbers bp_{1} … p_{i−1} are also in T, and p_{i} is in P_{bp_{1}...p_{i−1}}.

(c) The (second kind) basic elements of T are

• 1 and 6 if P ≡ ±1 (mod 6), Q ≡ −1 (mod 6);

• 1 only, otherwise.

As in Theorem 1, the primes in part (b) of Theorem 12 need not be distinct. Note that parts (a) and (b) of the theorem imply that, unless 2 is special, no element of T is divisible by 4. Again, Somer [21, Theorem 4] had many results concerning the set T. In particular, he already noted the importance of 6 for its structure.

We now compare P_{T,n} and P_{T,np}, as we did P_{S,n} and P_{S,np}. But, in this case, the prime 2 is, unsurprisingly, anomalous.

Corollary 13. (a) For an odd prime p in P_{T,n}, we have p ∈ P_{T,np};

(b) For q an odd prime with q ∈ P_{T,n}, we have q ∈ P_{T,2n} if and only if q | Q;

(c) For 2 ∈ P_{T,n}, we have 2 ∈ P_{T,2n} if and only if 2 is special.

Proof. Part (a) follows from the fact that for p odd v_{n} | v_{np} , combined with Theorem 12(a). For (b), we know from Theorem 12(a) that q | v_{n}. Then from v_{2n} = v_{n}^{2} − 2Q^{n} we see that q | v_{2n} iff q | Q. For (c), we know from Theorem 12(a) that for 2 ∈ P_{T,2n} all prime divisors of 2n are special, so 2 is special. Conversely, if 2 is special, then all prime factors of 2n are special, and P is even, so that, by Theorem 12(a), 2 ∈ P_{T,2n}.

Corollary 14. If n ∈ T and

• all odd prime factors of m divide v_{n};

and

• if m is even then every prime divisor of nm is special;

then nm ∈ T.

Proof. On successively multiplying n by first the odd and then the even prime divisors of m, we see from Theorem 12(a) that the stated conditions ensure that we stay within T while doing this.

This result extends Theorem 5(i) of Somer [21], which has the condition that ‘m is a product of special primes or divides n’ instead of ‘all odd prime factors of m divide v_{n}’.

5 Preliminary results for T.

We first quote the important result of Somer for T, corresponding to his result (Theorem 3 above) for S.

Theorem 15 (Somer [21, Theorem 5]). Theorem 3 holds with the set S replaced by the set T.

Jarden [13, Theorem E] proved this result for the classical Lucas sequence (i.e., P = 1, Q = −1) under the restriction p_{max} ≠ 3.

Lemma 16. Suppose q is a special prime. Then q^{e_{n}} | v_{n}, where e_{n} ≥ ⌊log_{q} n⌋.

Proof. From the recurrence, it is easy to see that we can take

e_{n} = \begin{cases}⌊\frac{n}{2}⌋ + 1, if q = 2; \\ ⌊\frac{n+1}{2}⌋ , if q ≥ 3, \end{cases}

the slightly higher value for q = 2 coming from the fact that v_{0} = 2. Then use ⌊log_{q} n⌋ ≤ ⌊\frac{n+1}{2}⌋.

We then immediately obtain the following.

Corollary 17 (Special case of Somer [21, Theorem 5(i)]). If n is a product of special primes then it belongs to T.

We can now extend Theorem 15 as follows.

Proposition 18. If ℓ ≥ 2 and 2^{ℓ} · 3 ∈ T, then 2^{ℓ} ∈ T.

Proof. Put L = 2^{ℓ}. If 2 is special, then, by Corollary 17, L ∈ T for all ℓ ≥ 1. So we can assume that 2 is not special. We then know that Q must be odd, as if it were even then we would have 2 | v_{3L} and v_{3L} ≡ P^{3L} (mod Q), so P would be even and 2 special.

From L | v_{3L} = v_{L}(v_{L}^{2} − 3Q^{L}) we see that if v_{L} were odd then, as L is even, Q^{L} is a square, and so v_{L}^{2} − 3Q^{L} ≡ 2 (mod 4), giving 2^{1}∥v_{3L}, a contradiction. Hence v_{L} is even, and L | v_{L}.

Next, we consider the set P_{T} of primes that divide some n ∈ T. To set our result in context, recall that P_{2nd} denotes the set of the primes dividing v_{n} for some n ≥ 1. Clearly P_{T} is a subset of P_{2nd}. Our next result, essentially dating back to Lucas [15], describes this set. See also Somer [21, Proposition 2(iv)].

Proposition 19. The set P_{2nd} is a proper subset of P_{1st}. It consists of

• the primes p for which the rank of appearance ω(p) of p (in (u_{n})) is even;

• the special primes;

• the prime 2, unless P is odd and Q is even.

Proof. Take a prime p with p ∤ 2Q, and let ω = ω(p). If ω is even, then the identity u_{2n} = u_{n}v_{n} for n = ω/2 shows that p | v_{n}, p ∈ P_{2nd}. The identity also shows that P_{2nd} ⊂ P_{1st}.

Conversely, if p ∈ P_{2nd}, say p | v_{n}, then p | u_{2n}, so that, by [20, Proposition 1(iv)], ω | 2n. However, from the identity

u_{n}^{2} − Δv_{n}^{2} = 4Q^{n},  (6)

we have p ∤ u_{n}, so that ω is even.

Now take a prime p with p | Q. Then from v_{n} ≡ P^{n} (mod p) we see that, for p to be in P_{2nd}, p must be special. In particular, 2 ∉ P_{2nd} when P is odd and Q is even. Further, if P is even then v_{1} = P is even, while if P and Q are both odd then v_{3} = P (P^{2} − 3Q) is even.

Finally, for p ∤ 2Q, choose m odd, and sufficiently large that we can take p to be a primitive prime divisor of u_{m}. Then we have ω(p) = m, and hence p ∈ P_{1st} \ P_{2nd}.

Our next lemma is an easy exercise. Dickson [8, pp. 67 and 271] traces the result back to an ‘anonymous writer’ in 1830 [25], and also to Lucas [15, p. 229].

Lemma 20. For p an odd prime and j = 1, 2, …, (p − 1)/2, the expression B_{j} := \binom{p−1}{j} − (−1)^{j} is divisible by p.

The following result essentially dates back to Lucas [15, p. 210] and Carmichael [6, Theorem X].

Lemma 21. (i) For n ∈ ℕ and any prime p, p divides v_{np} if and only if p divides v_{n}.

(ii) For n ∈ ℕ and any odd prime p, v_{n} divides v_{np} and v_{np}/v_{n} ≡ v_{n}^{p−1} (mod p).

Proof. (i) Now v_{2} = v_{1}^{2} − 2Q, which is even iff v_{1} is even. Also, for p ≥ 3,

v_{1}^{p} = (α + β)^{p} = v_{p} + ∑_{j=1}^{(p−1)/2}\binom{p}{j}Q^{j}v_{p−2j} ≡ v_{p} (mod p).  (7)

Now replace α, β by α^{n}, β^{n}.

(ii) Taking p odd and B_{j} defined as in Lemma 20, we have

v_{p} = (α + β)(α^{p−1} − α^{p−2}β + ⋯ + β^{p−1})

= (α + β)((α + β)^{p−1} − ∑_{j=1}^{p−2} B_{j}α^{p−1−j}β^{j})

= v_{1} (v_{1}^{p−1} − ∑_{j=1}^{(p−3)/2}B_{j}Q^{j}v_{p−1−2j} − B_{(p−1)/2}Q^{(p−1)/2}) .

so that the result of p odd follows by replacing α, β by α^{n}, β^{n} and using Lemma 20.

6 Proof of Theorem 12

We now prove part (a) of Theorem 12. First take p odd and n ∈ T. Then, by Lemma 21(i), if p ∤ v_{n} then p ∤ v_{np}, so np ∉ T. Conversely, if p^{λ}∥v_{n} for some λ ≥ 1 then by Lemma 21(ii) p^{λ+1} | v_{np}. Since n | v_{n} and pv_{n} | v_{np} we have np ∈ T.

Now take p = 2, and suppose that both n and 2n are in T. First note that v_{n} must be even, as otherwise v_{2n} = v_{n}^{2} − 2Q^{n} would be odd. Also, we have n | Q^{n}, so that every prime factor q of n divides Q. (Note that this works too if q = 2, as then 4 | v_{2n}.) But q must also divide P, as otherwise v_{n} ≡ P^{n} ≢ 0 (mod q). Hence q is special, and n is a product of special primes. If n is even, then 2 is special, so P and Q are both even. If n is odd then, because v_{n} is even, we must have either P even and Q odd or (from the recurrence) P and Q both odd and 3 | n. So we have either P even or Q odd and 3 | n.

Conversely, assume that n ∈ T is a product of special primes, and either P is even or (Q is odd and 3 | n). We know from Corollary 17 that every product of special primes is in T. So if 2 is special, then 2n ∈ T. So we can assume 2 is not special, and hence that n is odd. If P is even, then, from the recurrence, all the v_{k}, in particular v_{n} and v_{2n}, are even. Also, if P and Q are both odd and 3 | n, then v_{n} and v_{2n} = v_{n}^{2} − 2Q^{n} are both even. Since for every prime factor q of n with q^{λ}∥n we have λ ≤ log_{q} n < n, so that n | Q^{n}. Hence 2n | v_{2n}, 2n ∈ T.

The proof of part (b) is just the same as that for Theorem 1(b).

To prove part (c): we see easily from Theorem 15 and Proposition 18 that the only possible (second kind) basic numbers are 1 and 6. To find the conditions on P and Q that make 6 basic, we assume that 6 ∈ T but 2 ∉ T, 3 ∉ T. Then v_{2} = P^{2} − 2Q is odd, so P is odd. Also 3 ∤ v_{3} = P (P^{2} − 3Q), so P ≡ ±1 (mod 6). From 6 | v_{6} = v_{2}(v_{2}^{2} − 3Q^{2}) we have Q odd and 3 | v_{2} ≡ 1 − 2Q (mod 3), so that Q ≡ −1 (mod 6). Conversely, if P ≡ ±1 (mod 6) and Q ≡ −1 (mod 6) then it is easily checked that 6 is basic. This proves part (c).

7 Finiteness results for S and for T.

In this section we look at when S, P_{S}, and T, P_{T} are finite. The results given here are essentially reformulations of results of Somer [20], [21].

Theorem 22. The set S is finite if and only if Δ = 1, in which case S = {1}. For S infinite, P_{S} is finite when Q = 0 and P ≠ 0, in which case P_{S} consists of the prime divisors of P. Otherwise, P_{S} is also infinite. Furthermore, P_{S} is the set P of all primes if and only if every prime divisor of Q is special. (This includes the case Q = ±1.)

For the proof, we note first that when Δ = 1, α and β are consecutive integers, and 1 is the only basic element. But there are no primes p dividing u_{1}Δ = 1, so P_{S,1} is empty, and S = {1}. In all other cases, |u_{1}Δ| > 1, P_{S,1} is nonempty, with p ∈ P_{S,1} say, and then, by Corollary 2, p^{k} ∈ S for all k ≥ 0, making S infinite.

Now assume S is infinite. We recall that (u_{n})_{n≥0} is called degenerate if Q = 0 or α/β is a root of unity. (The latter alternative includes the case P = 0, Q ≠ 0.) We consider the two cases of (u_{n}) being degenerate or nondegenerate separately. If (u_{n}) is degenerate, then by [20, Theorem 9] either

• P ≠ 0 and Q = 0, so that then S consists of those n whose prime factors all divide P, and P_{S} = P_{1st} is the set of prime divisors of P;

or

• for some r = 1, 2, 3, 4 or 6, S has a subset {rk : k ∈ ℕ} where u_{rk} = 0, so that P_{S} = P_{1st} = P.

Now consider the case of (u_{n}) nondegenerate. Then, by Somer [20, Theorem 1], all but finitely many u_{n} have a primitive prime divisor (a prime dividing u_{n} that do not divide u_{m} for any m < n). So, using Theorem 1(a), P_{S} is infinite. Somer’s theorem is based on results of Lekkerkerker [14] and Schinzel [18]. In fact Bilu, Hanrot and Voutier [5] have proved that for such sequences with no special primes every u_{n} with n > 30 has a primitive divisor. They also listed exceptions with n ≤ 30. Hence u_{p^{k}} has a primitive prime divisor for all sufficiently large k, making P_{S} infinite. See Abouzaid [1] for corrections to their list. Also Stewart [22] and Shorey and Stewart [19] gave lower bounds for the largest prime divisor of u_{n}.

This proof will be complete after we have proved the following. While this result is contained in Somer [20, Theorem 8], we give another proof here.

Proposition 23. The set P_{S} is the whole of P if and only if all primes are regular.

Proof. First note that if there are any irregular primes then, by Corollary 7, P_{S}, being a subset of P_{1st}, cannot be the whole of P.

Conversely, assume all primes are regular, so that any prime factor p of Q also divides P. Note that then p | Δ. To show that all primes belong to P_{S}, we proceed by induction. We first show that 2 ∈ P_{S}. If u_{2} = P is even, then 2 ∈ S, 2 ∈ P_{S}. So we can take P odd. Then Q must be odd, too, by our assumption. Then u_{3} = P^{2} − Q is even, and hence so is u_{6} = u_{3}v_{3}. We claim that either 3 | u_{6}, in which case 6 ∈ S, 2, 3 ∈ P_{S}, or 12 ∈ S, with the same implication.

• If P ≡ 3 (mod 6), Q ≡ 3 (mod 6), then 3 | u_{n} for all n ≥ 2, so that 3 | u_{6}.

• If P ≡ 3 (mod 6), Q ≡ ±1 (mod 6), then 6 is basic, by Theorem 1(c).

• If P ≡ ±1 (mod 6), Q ≡ −1 (mod 6), then 12 is basic, by Theorem 1(c).

• If P ≡ ±1 (mod 6), Q ≡ 1 (mod 6), then 3 | u_{3} and so 3 | u_{3}v_{3} = u_{6}.

Hence 2 ∈ P_{S}, as claimed.

We now assume that q ∈ P_{S} for every prime q < p, where p is a prime at least 3. We have just shown that this is true for p = 3. By Lemma 8, we know that for any exponents ε_{q} = 0 or 1 there is a positive integer k such that k ∏_{q<p} q^{ε_{q}} ∈ S; hence, by Corollary 2, k ∏_{q<p} q^{e_{q}} ∈ S for any exponents e_{q} ≥ ε_{q}.

By Lemma 6, p | u_{p+ε}, for some ε = ±1. As p > 2, all prime factors of p + ε are less than p so, by the induction hypothesis, k(p + ε) ∈ S for some k. If p | k then p ∈ P_{S}. If p ∤ k then, using (1), we have

u_{pk(p+ε)} = u_{p}^{(k(p+ε))}u_{k(p+ε)} = u_{pk}^{(p+ε)}u_{p+ε},

so that pk(p + ε) ∈ S, p ∈ P_{S}. This proves the induction step.

This completes the proof of Theorem 22.

We now consider the finiteness (or otherwise) of T and P_{T}.

Theorem 24 (Somer [21, Theorems 8 and 9]). The set T is finite in the following two cases:

• P = ±1, Q ≢ −1 (mod 6), in which case T = {1};

• P = ε_{1}2^{k}, Q = 2^{2k−1} + ε_{2}, where k is a positive integer, and ε_{1}, ε_{2} ∈ {−1, 1}, in which case T = {1, 2}.

Otherwise, T is infinite. For T infinite, P_{T} is finite precisely when P, Q are not both 0 and either

• P^{2} = Q, in which case P_{T} is the set of prime divisors of 2P

or

• P^{2} = 4Q or Q = 0, in which case P_{T} is the set of prime divisors of P.

Otherwise, for T infinite, P_{T} is also infinite.

Proof. If T contains an integer n having an odd prime factor p then, by Theorem 12(a), p^{k}n ∈ T for all k ≥ 0. In particular, if P = ±1 and Q ≡ −1 (mod 6), then 6 ∈ T, so that T is infinite. On the other hand, if P = ±1 and Q ≢ −1 (mod 6), then 1 is the only basic element of T, and v_{1} = P has no prime factors so that, by Theorem 12(a), P_{T,1} is empty, and hence T = {1}.

Again starting with 1 ∈ T, we see that T is infinite if P has any odd prime factors. Also, T is infinite if P is ± a positive power of 2 and 2 is special, as then 2^{k} ∈ T for all k ≥ 0, by Theorem 12(a).

It therefore remains only to consider the case of P = ±2^{k}, k ≥ 1 and Q odd, so that 2 is not special. Then 2 ∈ T and 4 ∉ T, by Theorem 12(a). If v_{2} has an odd prime factor p, then 2p^{k} ∈ T for all k ≥ 0, so that T is again infinite. Finally, if v_{2} is ± a power of 2, then T = {1, 2}. This happens only when v_{2} = 2^{2k} − 2Q = ±2, so that Q = 2^{2k−1} ∓ 1, as claimed.

Now take T infinite, with P, Q not both 0. If the sequence (v_{n}) is degenerate, then, using Somer [21, Theorem 9], we get either P^{2} = Q, P^{2} = 4Q or Q = 0, and P_{T} being the set of prime divisors of P, as required. On the other hand, if (v_{n}) is not degenerate then by Somer [21, Theorem 1] for sufficiently large n every v_{n} has a primitive prime divisor. Hence we can find an infinite sequence of numbers n in T such that np is again in T, where p is a primitive prime divisor of v_{n}. (Here we are using Theorem 12(a).) Thus P_{T} then contains infinitely many primes p.

8 The sets P_{S} and P_{T}.

From the proof of Theorem 22 we see that P_{S} = P_{1st} for (u_{n}) degenerate or all primes being regular. Our next result takes care of the remaining cases. I thank Larry Somer and the referee for pointing out how the proof of this could be completed.

Proposition 25. If (u_{n}) is nondegenerate and there are irregular primes, then P_{S} is a proper subset of P_{1st}.

Proof. Take (u_{n}) nondegenerate and having an irregular prime f. Then, from the discussion preceding Proposition 23, every u_{n} for n sufficiently large has a primitive prime divisor. Indeed, if gcd(P, Q) = 1 this is true for n > 30. Hence for ℓ sufficiently large, u_{ℓf} has a primitive prime divisor, p say, so that ω(p) = ℓf.

Then if, for some k, kp were in S, we would have kp | u_{kp}, so that, by [20, Proposition 1(iv)], ω(p), and hence f, would divide kp. Hence f would divide u_{n}, contradicting Corollary 7. Thus p ∉ P_{S}.

We have in fact shown that no prime whose rank of appearance is a multiple of any irregular prime f will belong to P_{S}. The referee has remarked that, when α/β is rational, the density of such primes has been precisely computed in many cases. For f > 2 and α/β not an f-th power, it is f/(f^{2} − 1). See Ballot [4, Theorem 3.2.3] and also Moree [16].

Using a similar method, we can also prove the corresponding result for T.

Proposition 26. The set P_{T} is a proper subset of P_{2nd}.

Proof. Let f be a primitive prime divisor of u_{n} for some odd n with f ∤ 2Q. Then, by Proposition 19, f ∈ P_{1st} \ P_{2nd}. Now, taking ℓ sufficiently large, let p be a primitive prime divisor of u_{2ℓf}. Then, as u_{2ℓf} = u_{ℓf}v_{ℓf}, p | v_{ℓf}. Suppose p ∈ P_{T}, so that, for some k, kp ∈ T, and hence kp | v_{kp}. But then by Somer [21, Proposition 2(vii)], kp is a multiple of ℓf. In particular, f | v_{kp}, contradicting f ∉ P_{2nd}. So p ∉ P_{T}.

9 Divisibility properties of S and of T.

From Theorem 1 we can consider S as a graph spanned by a forest of one or two trees, with each node corresponding to an element of S, and the root nodes of the trees being {1}, {1, 6} or {1, 12}. Each edge can be labelled p; it rises from a node n ∈ S to a node np ∈ S, where p is some prime divisor of u_{n}Δ. One spanning forest is obtained by taking only the edges n → np, where p is the largest prime factor of np such that n ∈ S. (By Theorem 3 and Proposition 4, p is either p_{max} or 2). Thus every node above n in the tree is divisible by n. Next, call a cutset of the forest a set C of nodes with the property that every path from a root to infinity must contain some vertex of the cutset. Then we clearly have the following.

Proposition 27. For a cutset C of S, every element of S either lies below C, or it is divisible by some node of C.

Judicious choice of a cutset places severe divisibility restrictions on elements of S, and so, using this, one can search for elements of S up to a given bound very efficiently.

The same argument applies equally to T, using Theorem 12, with p being either an odd prime divisor of v_{n} or, under the conditions described in that theorem, the prime 2. For instance, applying this idea to the sequence T of example 2 below, every element of that sequence except 1, 3, 9, 27 and 81 is divisible either by 171 or 243 or 13203 or 2354697 or 10970073 or 22032887841. See [3] for details.

10 Examples

1. P = 1, Q = −1 (the classical Fibonacci and Lucas numbers.) Here Δ = 5,

S = 1, 5, 12, 24, 25, 36, 48, 60, 72, 96, 108, 120, 125, 144, 168, 180, …,

with 1 and 12 basic (\underline{A023172} in Neil Sloane’s Encyclopedia), while P_{S} is the whole of P (see Theorem 22),

T = 1, 6, 18, 54, 162, 486, 1458, 1926, 4374, 5778, 13122, 17334, …,

with 1 and 6 basic (\underline{A016089}), and

P_{2nd} = 2, 3, 7, 11, 19, 23, 29, 31, 41, 43, 47, 59, 67, 71, 79, 83, 101, 103, 107, 127, …,

(A140409) of which P_{T} is a subsequence:

P_{T} = 2, 3, 107, 1283, 8747, 21401, 34667, 46187, …,

(A129729).

2. P = 3, Q = 2, where u_{n} = 2^{n} − 1, v_{n} = 2^{n} + 1. Here S = {1} as Δ = 1, and

T = 1, 3, 9, 27, 81, 171, 243, 513, 729, 1539, 2187, 3249, …,

with 1 basic (\underline{A006521}). Also

P_{2nd} = 3, 5, 11, 13, 17, 19, 29, 37, 41, 43, 53, 59, 61, 67, 83, 97, 101, 107, 109, …,

(\underline{A014662} – see also \underline{A091317}), of which

P_{T} = 3, 19, 163, 571, 1459, 8803, 9137, 17497, 41113, …

(\underline{A057719}) is a subsequence. Note too that, by Proposition 11 and the fact that all n ∈ T are odd, we have T = S(−1, −2). Also S = T (−1, −2) = {1}.

3. P = 3, Q = 5, Δ = −11,

S = 1, 6, 11, 12, 18, 24, 36, 48, 54, 66, 72, 96, 108, 121, 132, 144, 162, 168, 192, 198, …

with 1 and 6 basic, with P_{1st} consisting of all primes except the irregular prime 5, and

P_{S} = 2, 3, 7, 11, 13, 17, 23, 37, 41, 43, 67, 71, 73, 83, 89, 97, 101, 103, 107, 113, ….

Also

T = 1, 3, 9, 27, 81, 153, 243, 459, 729, 1377, 2187, 2601, 4131, 4401, 6561, 7803, …

with only 1 basic,

P_{2nd} = 2, 3, 7, 13, 17, 19, 23, 37, 43, 47, 53, 67, 73, 79, 83, 97, 103, 107, 113, …

and

P_{T} = 2, 3, 17, 103, 163, 373, 487, 1733, ….

11 Additional remarks.

1. It would be interesting to see whether the analysis of the paper could be extended to other second-order recurrence sequences, or indeed to any recurrences of higher order.

2. In [3], what we called ‘primitive’ solutions of n | 2^{n} + 1 should in fact have been called fundamental solutions, following Jarden [13, p. 70] and Somer [20, p. 522], [21, p. 482]. However, this definition has been superseded by the notion of a basic element (of S or of T) as in this paper.

3. In example 1 of Section 10 above we have 24 and 25 ∈ S = S(1, −1). Are these the only consecutive integers in S(1, −1)?

12 Acknowledgements

I am very grateful to both Larry Somer and the referee for their detailed contructive comments on an earlier version of this paper. Also, I thank Joe Silverman for a helpful comment.

References

[1] Mourad Abouzaid, Les nombres de Lucas et Lehmer sans diviseur primitif, J. Théor. Nombres Bordeaux 18 (2006), 299–313.

[2] Richard André-Jeannin, Divisibility of generalized Fibonacci and Lucas numbers by their subscripts, Fibonacci Quart. 29 (1991), 364–366.

[3] Toby Bailey and Chris Smyth, Primitive solutions of n | 2^{n} + 1, 2pp., linked from

http://www.research.att.com/∼njas/sequences/A006521, 2008.

[4] Christian Ballot, Density of prime divisors of linear recurrences, Mem. Amer. Math. Soc. 115 (1995), no. 551, 102pp.

[5] Yu. Bilu, G. Hanrot, and P. M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers, J. Reine Angew. Math. 539 (2001), 75–122.

[6] R. D. Carmichael, Note on a recent problem in the American Mathematical Monthly, Amer. Math. Monthly 14 (1907), 8–9.

[7] R. D. Carmichael, On the numerical factors of the arithmetic forms α^{n} ± β^{n}, Ann. of Math. (2) 15 (1913/14), 30–70.

[8] Leonard Eugene Dickson, History of the Theory of Numbers. Vol. I: Divisibility and primality., Chelsea Publishing Co., New York, 1966.

[9] Graham Everest, Alf van der Poorten, Igor Shparlinski, and Thomas Ward, Recurrence Sequences, Mathematical Surveys and Monographs, vol. 104, American Mathematical Society, Providence, RI, 2003.

[10] Kálmán Győry, Az a^{n} ± b^{n} alakú számok osztóiról két számelméleti feladat kapcsán [On divisors of numbers of the form a^{n}±b^{n}], Középiskolai Matematikai Lapok [Mathematical Journal for Secondary Schools] 41 (1991), 193–201.

[11] Kálmán Győry and Chris Smyth, The divisibility of a^{n} − b^{n} by powers of n, to appear.

[12] Verner E. Hoggatt, Jr. and Gerald E. Bergum, Divisibility and congruence relations, Fibonacci Quart. 12 (1974), 189–195.

[13] Dov Jarden, Divisibility of Fibonacci and Lucas numbers by their subscripts, Recurring Sequences: A Collection of Papers, Second edition. Revised and enlarged, Riveon Lematematika, Jerusalem (Israel), 1966, pp. 68–75.

[14] C. G. Lekkerkerker, Prime factors of the elements of certain sequences of integers. I, II, Nederl. Akad. Wetensch. Proc. Ser. A. 56 = Indagationes Math. 15 (1953), 265–276, 277–280.

[15] Edouard Lucas, Théorie des fonctions numériques simplement périodiques, Amer. J. Math. 1 (1878), 184–196, 197–240, 289–321.

[16] Pieter Moree, On primes p for which d divides ord_{p}(g), Funct. Approx. Comment. Math. 33 (2005), 85–95.

[17] Paulo Ribenboim, The Fibonacci numbers and the Arctic Ocean, Proceedings of the 2nd Gauss Symposium. Conference A: Mathematics and Theoretical Physics (Munich, 1993), Sympos. Gaussiana, de Gruyter, Berlin, 1995, pp. 41–83.

[18] Andrzej Schinzel, The intrinsic divisors of Lehmer numbers in the case of negative discriminant, Ark. Mat. 4 (1962), 413–416 (1962).

[19] T. N. Shorey and C. L. Stewart, On divisors of Fermat, Fibonacci, Lucas and Lehmer numbers. II, J. London Math. Soc. (2) 23 (1981), 17–23.

[20] Lawrence Somer, Divisibility of terms in Lucas sequences by their subscripts, Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992), Kluwer Acad. Publ., Dordrecht, 1993, pp. 515–525.

[21] Lawrence Somer, Divisibility of terms in Lucas sequences of the second kind by their subscripts, Applications of Fibonacci numbers, Vol. 6 (Pullman, WA, 1994), Kluwer Acad. Publ., Dordrecht, 1996, pp. 473–486.

[22] C. L. Stewart, On divisors of Fermat, Fibonacci, Lucas, and Lehmer numbers, Proc. London Math. Soc. (3) 35 (1977), 425–447.

[23] Gary Walsh, On integers n with the property n | f_{n}, 5pp., unpublished, 1986.

[24] Hugh C. Williams, Édouard Lucas and Primality Testing, Canadian Mathematical Society Series of Monographs and Advanced Texts, 22, John Wiley & Sons Inc., New York, 1998, A Wiley-Interscience Publication.

[25] Anonymous Writer, Théorèmes et problèmes sur les nombres, J. Reine Angew. Math. 6 (1830), 100–106.

2000 Mathematics Subject Classification: Primary 11B39. Keywords: Lucas sequences, indices.

(Concerned with sequence \underline{A006521}, \underline{A014662}, \underline{A016089}, \underline{A023172}, \underline{A057719}, \underline{A091317}, \underline{A129729}, and \underline{A140409}.)

Received August 21 2009; revised version received January 29 2010. Published in Journal of Integer Sequences, January 31 2010.

Return to Journal of Integer Sequences home page.