Appearance of Primes in Fourth-Order Odd Divisibility Sequences

E. L. Roettger Department of General Education Mount Royal University 4825 Mount Royal Gate SW Calgary, AB T3E 6K6 Canada

                 eroettger@mtroyal.ca

H. C. Williams Department of Mathematics and Statistics University of Calgary 2500 University Drive NW Calgary, AB T2N 1N4 Canada

                 hwilliam@ucalgary.ca

Abstract

Let (A_{n}) denote any odd, non-degenerate, non-null, fourth-order linear divisibility sequence and let p be any prime such that p divides some term A_{n} (n > 1) of (A_{n}). In this paper we derive a number of properties of (A_{n}). In particular, we exhibit conditions which guarantee that if p | A_{k}, then ω | k. Here ω (= ω(p)) is the least positive integer m such that p | A_{m}.

Dedicated to the memory of Richard Guy (1916–2020).

1 Introduction

Although we use the notation (T_{n}) to denote the sequence

…, T_{−n}, …, T_{−2}, T_{−1}, T_{0}, T_{1}, T_{2}, …, T_{n}, …,

we will often be concerned in the sequel with terms of (T_{n}) which have only positive subscripts. Let p, q ∈ ℂ and α, β be the zeros of x^{2} − px + q ∈ ℂ[x]. We define, for any n ∈ ℤ,

u_{n} = u_{n}(p, q) = \frac{α^{n} − β^{n}}{α − β} , v_{n} = v_{n}(p, q) = α^{n} + β^{n}.

When p, q are integers, both u_{n}(p, q) and v_{n}(p, q) are integers for all n ≥ 0 and when p, q are coprime integers are called the Lucas functions. Note that u_{0} = 0, u_{1} = 1, v_{0} = 2, v_{1} = p. The Lucas sequences (u_{n}(p, q)), (v_{n}(p, q)) both satisfy the second-order linear recurrence

T_{n+1} = pT_{n} − qT_{n−1}.

Also, m | n ⇒ u_{m}(p, q) | u_{n}(p, q).

Definition 1. A linear recurrence sequence of order l over the integers is a sequence (T_{n}), where we have

T_{n+l} = A_{1}T_{n+l−1} + A_{2}T_{n+l−2} + A_{3}T_{n+l−3} + … + A_{l}T_{n}

and T_{0}, T_{1}, T_{2}, …, T_{l−1}, A_{1}, A_{2}, A_{3}, …, A_{l} are given fixed integers, with A_{l} ≠ 0. Furthermore, if T_{m} | T_{n} whenever m | n, then (T_{n}) is said to be a l^{th} order linear divisibility sequence (LDS).

Thus, we see that the Lucas sequence (u_{n}(p, q)) is a second-order LDS.

In his investigation of the problem of primality testing, Lehmer [4] introduced the functions (ū_{n}(r, q)), (v̄_{n}(r, q)), where r, q are coprime integers. These are defined by

ū_{n}(r, q) = \begin{cases}u_{n}(\sqrt{r}, q), & if 2 ∤ n; \\ \frac{u_{n}(\sqrt{r}, q)}{\sqrt{r}}, & if 2 | n, \end{cases}

v̄_{n}(r, q) = \begin{cases}v_{n}(\sqrt{r}, q), & if 2 | n; \\ \frac{v_{n}(\sqrt{r}, q)}{\sqrt{r}}, & if 2 ∤ n. \end{cases}

Notice that for n positive or negative

ū_{−n}(r, q) = −q^{n}ū_{n}(r, q), v̄_{−n}(r, q) = q^{n}v̄_{n}(r, q).

The sequences (ū_{n}(r, q)), (v̄_{n}(r, q)) are comprised of integers for all n ≥ 0 and both satisfy the fourth-order linear recurrence

T_{n+4} = (r − 2q)T_{n+2} − q^{2}T_{n}.  (1)

Here we have ū_{0} = 0, ū_{1} = 1, ū_{2} = 1, ū_{3} = r − q, v̄_{0} = 2, v̄_{1} = 1, v̄_{2} = r − 2q, v̄_{3} = r − 3q. Furthermore, (ū_{n}(r, q)), is a divisibility sequence; hence (ū_{n}(r, q)) is a fourth-order LDS. We also know from results in [4] that ū_{2n}(r, q) = ū_{n}(r, q)v̄_{n}(r, q) and that v̄_{n}(r, q) | v̄_{kn}(r, q) when k is odd.

Recently, by making use of the theory of generalized Vandermonde determinants, Barbero [2] was able to give an elementary proof of an important result of Bézivin, Pethö, and van der Poorten [3] in the specific case where the characteristic polynomial F (x) (= x^{l} −A_{1}x^{l−1}− A_{2}x^{l−2} − … − A_{l}) of (T_{n}) has a non-zero discriminant, but his overall result is much more general than this.

Definition 2. We say that the sequence (T_{n}) is degenerate if α_{i}/α_{j} is a root of unity for any two distinct roots α_{i}, α_{j} of the characteristic polynomial F (x).

Theorem 3. If (T_{n}) is a non-degenerate LDS of order l whose characteristic polynomial has distinct roots α_{1}, …,α_{l}, then, for all n ≥ 0, we must have T_{n} | r_{n}, where

r_{n} = ∏(α_{i}^{n} − α_{j}^{n})/(α_{i} − α_{j})

and the product is taken over all i and j such that 1 ≤ i < j ≤ l.

Theorem 3 was used by Abrate et al. [1] to prove the following result.

Theorem 4. If (T_{n}) is a non-degenerate LDS of order 4, then its characteristic polynomial must be the form

x^{4} − P x^{3} + (R + 2Q)x^{2} − P Qx + Q^{2},

for some integers P, Q and R.

The above polynomial is the characteristic polynomial for the Lehmer functions for P = 0, Q = q, R = −r.

Definition 5. If (T_{n}) is a linear recurrence sequence, we say that an integer m (m > 1) is a null divisor of (T_{n}) if, for some minimal h > 0, we have m | T_{n} for all n ≥ h.

Definition 6. If (T_{n}) has a null divisor, it is said to be a null sequence.

In what follows we shall be concerned only with non-null sequences. For example, the condition gcd(p, q) = 1 ensures that both (u_{n}(p, q)) and (v_{n}(p, q)) are non-null sequences. Similarly, the condition that gcd(r, q) = 1 ensures that both (ū_{n}(r, q)) and (v̄_{n}(r, q)) are nonnull sequences. Also, our attention will be confined to fourth-order sequences (T_{n}) which are both non-degenerate and non-null. Furthermore, as was done in Williams and Guy [12], we will only consider the case of l = 4 and (T_{n}) a divisibility sequence. By Theorem 4, we need only consider

F (x) = x^{4} − P_{1}x^{3} + (P_{2} + 2Q)x^{2} − P_{1}Qx − Q^{2},  (2)

where P_{1}, P_{2} and Q are fixed integers, i.e.,

T_{n+4} = P_{1}T_{n+3} − (P_{2} + 2Q)T_{n+2} + P_{1}QT_{n+1} − Q^{2}T_{n}.  (3)

Note that if D (≠ 0) is the discriminant of F (x), then

D = EΔ^{2}Q^{2},  (4)

where

Δ = P_{1}^{2} − 4P_{2}, E = (P_{2} + 4Q)^{2} − 4QP_{1}^{2}.  (5)

See, for example, Williams and Guy [10]. Let ρ_{1}, ρ_{2} be the roots of the quadratic polynomial x^{2} − P_{1}x + P_{2} = 0. Since

F (x) = f_{1}(x)f_{2}(x),

where f_{i}(x) = x^{2} − ρ_{i}x + Q, we may assume that if α_{1}, β_{1}, α_{2}, β_{2} denote the four distinct roots of F (x), then

α_{1}β_{1} = α_{2}β_{2} = Q.  (6)

Definition 7. We say that if (T_{n}) satisfies (3), then (T_{n}) is even when T_{−n} = T_{n}/Q^{n} and (T_{n}) is odd when T_{−n} = −T_{n}/Q^{n} for all n.

Certainly, if (T_{n}) is odd, we must have T_{0} = −T_{0}/Q^{0} ⇒ T_{0} = 0 and QT_{−1} = −T_{1}. We now show that these two conditions are necessary and sufficient for (T_{n}) to be odd.

Theorem 8. If T_{0} = 0, then (T_{n}) is odd if and only if QT_{−1} = −T_{1}.

Proof. If (T_{n}) is odd, then QT_{−1} = −T_{1} from the definition. Suppose that QT_{−1} = −T_{1}. By (3) we have

T_{2} = P_{1}T_{1} − (P_{2} + 2Q)T_{0} + P_{1}QT_{−1} − Q^{2}T_{−2}
= P_{1}T_{1} − 0 − P_{1}T_{1} − Q^{2}T_{−2} = −Q^{2}T_{−2}.

Also,

T_{3} = P_{1}T_{2} − (P_{2} + 2Q)T_{1} + P_{1}QT_{0} − Q^{2}T_{−1} = P_{1}T_{2} − (P_{2} + Q)T_{1}

and since

T_{1} = P_{1}T_{0} − (P_{2} + 2Q)T_{−1} + P_{1}QT_{−2} − Q^{2}T_{−3},

we see that

−Q^{3}T_{−3} = QT_{1} − (P_{2} + 2Q)T_{1} + P_{1}T_{2}
= P_{1}T_{2} − (P_{2} + 2Q)T_{1} − Q^{2}T_{−1} = T_{3}.

Thus, T_{i} = −Q^{i}T_{−i} (i = 0, 1, 2, 3). If we assume that for some m ≥ 0 we have T_{m+i} = −Q^{m+i}T_{−(m+i)} (i = 0, 1, 2, 3) (this is certainly true for m = 0), we can see that T_{m} = −Q^{m}T_{−m}, T_{m+1+i} = −Q^{m+1+i}T_{−(m+1+i)} (i = 0, 1, 2). We can now use (3) to compute

T_{m+1+3} = −Q^{m+2}(P_{1}QT_{−(m+3)} − (P_{2} + 2Q)T_{−(m+2)} + P_{1}T_{−(m+1)} − T_{−m}).

Also, by (3), we have

T_{−m} = P_{1}T_{−(m+1)} − (P_{2} + 2Q)T_{−(m+2)} + P_{1}QT_{−(m+3)} − Q^{2}T_{−(m+4)}.

Putting this value of T_{−m} into the previous result, we get

T_{m+1+3} = T_{m+4} = −Q^{m+4}T_{−(m+4)} = −Q^{m+1+3}T_{−(m+1+3)}.

Thus, we find by induction that T_{n} = −Q^{n}T_{−n} for all n ≥ 0.

If T_{0} = P_{1} = 0 and T_{1} = QT_{−1}, we can show by using the above reasoning that

Q^{n}T_{−n} = (−1)^{n−1}T_{n}.

Thus, in this case we see that T_{n} is neither even nor odd.

We also have the following simple result, which extends an observation in [11, §1].

Proposition 9. Suppose (T_{n}) satisfies (3). Let η ∈ {1, −1} and suppose T_{j}^{∗} = η^{j−1}T_{j} (j = −1, 0, 1, 2). If P_{1}^{∗} = ηP_{1} and

T_{n+4}^{∗} = P_{1}^{∗}T_{n+3}^{∗} − (P_{2} + 2Q)T_{n+2}^{∗} + P_{1}^{∗}QT_{n+1}^{∗} − Q^{2}T_{n}^{∗},

then T_{n}^{∗} = η^{n−1}T_{n} for all n ≥ 1.

Proof. Follows easily by induction on n.

Suppose that P_{1} = 0. If (T_{n}) satisfies (3), we have

T_{n+4} = −(P_{2} + 2Q)T_{n+2} − Q^{2}T_{n}.  (7)

If (T_{n}) is to be a non-degenerate LDS, we must have

1 + QT_{−1} = 0 or 1 − QT_{−1} = 0

by results in [12, §3]. In the case of QT_{−1} = −1, then

T_{n} = \begin{cases}T_{2}ū_{n}(−P_{2}, Q), & if 2 | n; \\ ū_{n}(−P_{2}, Q), & if 2 ∤ n; \end{cases}

if QT_{−1} = 1, then

T_{n} = \begin{cases}T_{2}ū_{n}(−P_{2}, Q), & if 2 | n; \\ v̄_{n}(−P_{2}, Q), & if 2 ∤ n. \end{cases}

Note that in either event (T_{n}) is a divisibility sequence because (ū_{n}(−P_{2}, Q)) is a divisibility sequence, v̄_{n}(−P_{2}, Q) | v̄_{nk}(−P_{2}, Q) when k is odd and ū_{2n}(−P_{2}, Q) = ū_{n}(−P_{2}, Q)v̄_{n}(−P_{2}, Q).

Now if we define u_{n}^{∗} = ū_{n}(−P_{2} − 4Q, −Q), we see that since −P_{2} − 4Q + 2Q = −P_{2} − 2Q, then (u_{n}^{∗}) must satisfy (7). Also, u_{0}^{∗} = 0 = ū_{0}(−P_{2}, Q), u_{1}^{∗} = 1 = v̄_{0}(−P_{2}, Q), u_{2}^{∗} = 1 = ū_{2}(−P_{2}, Q), u_{3}^{∗} = −P_{2} − 3Q = v̄_{3}(−P_{2}, Q). It follows that if QT_{−1} = 1, then

T_{n} = \begin{cases}T_{2}u_{n}^{∗}, & if 2 | n; \\ u_{n}^{∗}, & if 2 ∤ n \end{cases}

and therefore (T_{n}) is an odd divisibility sequence when we replace Q by −Q.

As an example of this consider Q = −1, P_{2} = −1. We have T_{0} = 0, T_{1} = 1, T_{2} = 1, T_{3} = 4,

T_{n+4} = 3T_{n+2} − T_{n} (see Sloane [7, \underline{A005013} ])

and T_{n} = T_{−n}. Furthermore,

T_{n} = \begin{cases}F_{n}, & if 2 | n; \\ L_{n}, & if 2 ∤ n, \end{cases}  (8)

where F_{n} and L_{n} denote the n^{th} Fibonacci and Lucas numbers, respectively. Also, T_{n} = ū_{n}(5, 1).

Let Δ = SU^{2} and E = GV^{2}, where S, G, U, V are integers and S and G are both nonzero and square-free. Let (T_{n}) be any non-null linear divisibility sequence with characteristic polynomial F (x) given by (2) with D ≠ 0 and P_{1} ≠ 0. In [12] the following results are proved:

• There is one and only one even (T_{n}) for any given F (x);

• If S ≠ 1 and G ≠ 1, (T_{n}) is either even or odd;

• If S ≠ 1 and G ≠ 1 and G ≠ S, there can be no odd (T_{n});

• If S = 1 and G ≠ 1, then the only possible odd (T_{n}) is a Lucas sequence (u_{n}).

We can now partition the possible cases for which (T_{n}) can be an odd divisibility sequence as follows:

(i) S = G ≠ 1;

(ii) S = 1, G ≠ 1;

(iii) S ≠ 1, G = 1;

(iv) S = G = 1.

It is not known whether any (T_{n}) exist in cases (i) and (iii), but none are known and it seems most unlikely in case (iii).

As the problem of determining all even LDSs of order 4 is solved, we will devote the remainder of the paper to deriving some further properties of odd LDSs of order 4. Also, as a result of our earlier discussion, we may assume that P_{1} ≠ 0. Let (T_{n}) be any divisibility sequence satisfying (3) and p be any fixed prime such that p | T_{n} for some n > 0.

Definition 10. Let ω_{1} be the least positive integer such that p | T_{ω_{1}}. We define the increasing sequence ω_{1}, ω_{2}, …, ω_{j} ∈ ℤ by p | T_{ω_{i}} and ω_{i} ∤ ω_{j} (1 ≤ i < j). Each ω_{i} in this sequence is called a rank of appearance^{1} of p.

Definition 11. If p | T_{n} implies that ω_{1} | n, then p has a single rank of appearance in (T_{n}). Such a sequence is said to be monoapparitic modulo p and the prime p is said to be monoapparitic in (T_{n}).

In [8] Ward proved that primes have only finitely many ranks of appearance in a general LDS. In this paper we shall be concerned with the special case of an odd LDS of order 4.

With the exception of Section 2, we will reserve the notation (A_{n}) to denote an odd, non-null and non-degenerate LDS of order 4. By [12, Proposition 4.1] we may assume that gcd(P_{1}, P_{2}, Q) = 1. The purpose of this paper is to prove Theorem A below.

Theorem A. Let (A_{n}) satisfy (3) and let p be any prime such that p | A_{n} for some n > 1; p can have at most two ranks of appearance in (A_{n}). If p ∤ P_{1}, then p has only one rank of appearance (is monoapparitic) in (A_{n}) when p | QΔE. It is also monoapparitic if S = 1, G ≠ 1; S ≠ 1, G = 1; or S = G ≠ 1. In the case of S = G = 1, there are sequences (A_{n}) for which p (p ∤ P_{1}) can have two distinct ranks of appearance.

We will prove Theorem A by showing that it holds for each of the cases (i)–(iv). In Section 2 we derive a number of useful identity relations connecting (A_{n}) to some special sequences (X_{n}), (Y_{n}), (U_{n}) and (W_{n}). We also prove a version of Theorem 3 in the particular case of (A_{n}). In the following section we provide a number of simple results which allow for the determination of when a prime p is monoapparitic in (A_{n}) for certain special cases. We also show that in general a prime can have at most two ranks of appearance in (A_{n}). The remaining sections deal with the problem of when p can be monoapparitic in the cases that remain.

2 Odd divisibility sequences of order 4

We have already seen that odd LDSs of order 4 exist; for example, (ū_{n}(r, q)) is such a sequence. Furthermore, the sequences \underline{A215466} and \underline{A127595} in the On-line Encyclopedia of Integer Sequences (OEIS) (see Sloane [7]) are examples of odd LDSs of order 4 which are not Lehmer sequences. In what follows we will derive some results which must be true for (A_{n}) if (A_{n}) is simply an odd linear recurrence sequence of order 4. In the first part of this section we will develop some of the machinery needed throughout the paper. We then use these results to prove the main result of the section: Theorem 13. This theorem is a more specialized version of Theorem 3 and helps in discerning when (A_{n}) can and cannot be a divisibility sequence.

1Lucas used the term “le rang d’apparition” and the French word “apparition” has been–and still is– widely used among English writers. However, it is best to avoid the ghostly or miraculous connotation that the English word “apparition” possesses and use “appearance” instead.

We begin, as was done in [10] and [12], by defining the auxiliary sequences (W_{n}), (U_{n}), (X_{n}) and (Y_{n}) by

v_{n}(ρ_{i}, Q) = W_{n} + ρ_{i}U_{n} = α_{i}^{n} + β_{i}^{n}  (9)

and

u_{n}(ρ_{i}, Q) = X_{n} + ρ_{i}Y_{n} = \frac{α_{i}^{n} − β_{i}^{n}}{α_{i} − β_{i}};  (10)

here ρ_{i} = α_{i} + β_{i} (i = 1, 2). Also, ρ_{1}, ρ_{2} are the distinct roots of x^{2} − P_{1}x + P_{2} = 0. We point out here that X_{n} = U_{0,n}, Y_{n} = U_{1,n}, W_{n} = V_{0,n}, U_{n} = V_{1,n}, where the symbols U_{i,n}, V_{i,n} (i = 0, 1) are defined in [9, (10.1.5) and (10.1.6)] (with k = 2). Notice each of (W_{n}), (U_{n}), (X_{n}), (Y_{n}) satisfies (3). Also, the initial terms of these sequences are as follows:

W_{−1} = 0,  W_{0} = 2, W_{1} = 0, W_{2} = −P_{2} − 2Q, W_{3} = −P_{1}P_{2};
U_{−1} = \frac{1}{Q},  U_{0} = 0,  U_{1} = 1,  U_{2} = P_{1},  U_{3} = P_{1}^{2} − P_{2} − 3Q;
X_{−1} = \frac{−1}{Q},  X_{0} = 0,  X_{1} = 1,  X_{2} = 0,  X_{3} = −P_{2} − Q;
Y_{−1} = 0,  Y_{0} = 0,  Y_{1} = 0,  Y_{2} = 1,  Y_{3} = P_{1}.

Further,

(X_{n}), (Y_{n}), (W_{n}), (U_{n}) ⊆ ℤ (n ≥ 0).

By Theorem 8, we see that both (X_{n}) and (Y_{n}) are odd. Indeed, we have

X_{−n} = −X_{n}/Q^{n}, Y_{−n} = −Y_{n}/Q^{n}.

Also,

W_{−n} = W_{n}/Q^{n}, U_{−n} = U_{n}/Q^{n},

thus (W_{n}), (U_{n}) are even.

In [12] it is noted that if (A_{n}) is a LDS of order 4, then

A_{n} = X_{n} + A_{2}Y_{n};  (11)

however, this condition is not sufficient for (A_{n}) to be such a sequence. From Theorem 3 we can derive the following result.

Proposition 12. For (A_{n}) defined as above we must have

A_{n} | Q^{n−1}JY_{n}^{2}U_{n}^{2},

where J = A_{2}^{2} − P_{1}A_{2} + P_{2}.

Proof. By Theorem 3, we know that A_{n} must be a divisor of r_{n} for all n ≥ 0, where here

r_{n} = \frac{α_{1}^{n} − α_{2}^{n}}{α_{1} − α_{2}} · \frac{α_{1}^{n} − β_{1}^{n}}{α_{1} − β_{1}} · \frac{α_{1}^{n} − β_{2}^{n}}{α_{1} − β_{2}} · \frac{α_{2}^{n} − β_{1}^{n}}{α_{2} − β_{1}} · \frac{α_{2}^{n} − β_{2}^{n}}{α_{2} − β_{2}} · \frac{β_{1}^{n} − β_{2}^{n}}{β_{1} − β_{2}} .  (12)

Since

(ρ_{1} − ρ_{2})U_{n} = α_{1}^{n} + β_{1}^{n} − α_{2}^{n} − β_{2}^{n},

we find from (6), that

(ρ_{1} − ρ_{2})U_{n} = \frac{(α_{1}^{n} − α_{2}^{n})(α_{2}^{n} − β_{1}^{n})}{α_{2}^{n}} = \frac{(β_{1}^{n} − β_{2}^{n})(β_{2}^{n} − α_{1}^{n})}{β_{2}^{n}}.

Hence,

Q^{n}(ρ_{1} − ρ_{2})^{2}U_{n}^{2} = (α_{1}^{n} − α_{2}^{n})(β_{1}^{n} − β_{2}^{n})(α_{2}^{n} − β_{1}^{n})(β_{2}^{n} − α_{1}^{n});

also, for n = 1,

Q(ρ_{1} − ρ_{2})^{2} = (α_{1} − α_{2})(β_{1} − β_{2})(α_{2} − β_{1})(β_{2} − α_{1}).

Thus,

Q^{n−1}U_{n}^{2} = \frac{α_{1}^{n} − α_{2}^{n}}{α_{1} − α_{2}} · \frac{β_{1}^{n} − β_{2}^{n}}{β_{1} − β_{2}} · \frac{α_{2}^{n} − β_{1}^{n}}{α_{2} − β_{1}} · \frac{β_{2}^{n} − α_{1}^{n}}{β_{2} − α_{1}} .

By (10), we have

\frac{α_{1}^{n} − β_{1}^{n}}{α_{1} − β_{1}} · \frac{α_{2}^{n} − β_{2}^{n}}{α_{2} − β_{2}} = (X_{n} + ρ_{1}Y_{n})(X_{n} + ρ_{2}Y_{n}) = X_{n}^{2} − P_{1}X_{n}Y_{n} + P_{2}Y_{n}^{2}.

From these results and (11) we find that,

r_{n} = Q^{n−1}((A_{n} − A_{2}Y_{n})^{2} − P_{1}(A_{n} − A_{2}Y_{n})Y_{n} + P_{2}Y_{n}^{2})U_{n}^{2}
= Q^{n−1}(A_{n}^{2} − (2A_{2} + P_{1})A_{n}Y_{n} + JY_{n}^{2})U_{n}^{2},

where J = A_{2}^{2} − P_{1}A_{2} + P_{2} and r_{n} satisfies (12). Thus, we find that

A_{n} | Q^{n−1}JY_{n}^{2}U_{n}^{2} (for all n ≥ 0).

Later in this section we will improve this result showing that (A_{n}) is a divisibility sequence if and only if

A_{n} | JY_{n}U_{n} (for all n ≥ 0).

We will next establish some identities involving the sequences (A_{n}), (X_{n}), (Y_{n}), (W_{n}), (U_{n}). We begin with the well-known identity

(α_{i}^{n} + β_{i}^{n})^{2} − (α_{i} − β_{i})^{2} (\frac{α_{i}^{n} − β_{i}^{n}}{α_{i} − β_{i}} )^{2} = 4α_{i}^{n}β_{i}^{n} = 4Q^{n},  (13)

and get

(W_{n} + ρ_{i}U_{n})^{2} − (ρ_{i}^{2} − 4Q)(X_{n} + ρ_{i}Y_{n})^{2} = 4Q^{n}.  (14)

Setting n = 1 in (13) yields (α_{i} − β_{i})^{2} = (α_{i} + β_{i})^{2} − 4α_{i}β_{i} = ρ_{i}^{2} − 4Q. Since ρ_{i}^{2} = P_{1}ρ_{i} − P_{2}, we get

ρ_{i}^{2} − 4Q = P_{1}ρ_{i} − P_{2} − 4Q,
ρ_{i}(ρ_{i}^{2} − 4Q) = ρ_{i}(P_{1}ρ_{i} − P_{2} − 4Q) = (P_{1}^{2} − P_{2} − 4Q)ρ_{i} − P_{1}P_{2},

ρ_{i}^{2}(ρ_{i}^{2} − 4Q) = ρ_{i}^{2}(P_{1}ρ_{i} − P_{2} − 4Q) = P_{1}(P_{1}^{2} − P_{2} − 4Q)ρ_{i} − P_{2}(P_{1}^{2} − P_{2} − 4Q).

It follows from (14), that

W_{n}^{2} − P_{2}U_{n}^{2} + (P_{2} + 4Q)X_{n}^{2} + 2P_{1}P_{2}X_{n}Y_{n} + P_{2}(P_{1}^{2} − P_{2} − 4Q)Y_{n}^{2} = 4Q^{n},

2W_{n}U_{n} + P_{1}U_{n}^{2} − P_{1}X_{n}^{2} − 2(P_{1}^{2} − P_{2} − 4Q)X_{n}Y_{n} − P_{1}(P_{1}^{2} − 2P_{2} − 4Q)Y_{n}^{2} = 0.

From (11), we find by replacing A_{n} − A_{2}Y_{n} for X_{n} that

2W_{n}U_{n} + P_{1}U_{n}^{2} − P_{1}A_{n}^{2} + 2A_{n}LY_{n} − IY_{n}^{2} = 0  (15)

and

W_{n}^{2} − P_{2}U_{n}^{2} + (P_{2} + 4Q)A_{n}^{2} − 2A_{n}Y_{n}(A_{2}(P_{2} + 4Q) − P_{1}P_{2}) + KY_{n}^{2} = 4Q^{n}.  (16)

Here

I = P_{1}A_{2}^{2} − 2(P_{1}^{2} − P_{2} − 4Q)A_{2} + P_{1}(P_{1}^{2} − 2P_{2} − 4Q),  (17)
K = (P_{2} + 4Q)A_{2}^{2} − 2P_{1}P_{2}A_{2} + P_{2}(P_{1}^{2} − P_{2} − 4Q)  (18)

and

L = P_{1}A_{2} − P_{1}^{2} + P_{2} + 4Q.  (19)

From

2(X_{n+m} + ρ_{i}Y_{n+m}) = 2 (\frac{α_{i}^{n+m} − β_{i}^{n+m}}{α_{i} − β_{i}} )

= (\frac{α_{i}^{n} − β_{i}^{n}}{α_{i} − β_{i}} ) (α_{i}^{m} + β_{i}^{m}) + (\frac{α_{i}^{m} − β_{i}^{m}}{α_{i} − β_{i}} ) (α_{i}^{n} + β_{i}^{n})

= (X_{n} + ρ_{i}Y_{n})(W_{m} + ρ_{i}U_{m}) + (X_{m} + ρ_{i}Y_{m})(W_{n} + ρ_{i}U_{n}),

so we find that

2X_{n+m} = W_{n}X_{m} + W_{m}X_{n} − P_{2}(U_{n}Y_{m} + U_{m}Y_{n}),
2Y_{n+m} = U_{n}X_{m} + U_{m}X_{n} + W_{n}Y_{m} + W_{m}Y_{n} + P_{1}(U_{n}Y_{m} + U_{m}Y_{n}).

Multiplying the second of these by A_{2} and adding, we see since A_{n} = X_{n} + A_{2}Y_{n} that

2A_{n+m} = W_{n}A_{m} + W_{m}A_{n} + A_{2}(U_{n}A_{m} + U_{m}A_{n}) − J(U_{n}Y_{m} + U_{m}Y_{n}).  (20)

By using

2(W_{n+m} + ρ_{i}U_{n+m}) = 2(α_{i}^{n+m} + β_{i}^{n+m})

= (α_{i}^{n} + β_{i}^{n})(α_{i}^{m} + β_{i}^{m}) + (α_{i} − β_{i})^{2} (\frac{α_{i}^{n} − β_{i}^{n}}{α_{i} − β_{i}} ) (\frac{α_{i}^{m} − β_{i}^{m}}{α_{i} − β_{i}} )

= (W_{n} + ρ_{i}U_{n})(W_{m} + ρ_{i}U_{m}) + (ρ_{i}^{2} − 4Q)(X_{n} + ρ_{i}Y_{n})(X_{m} + ρ_{i}Y_{m}),

we get

2W_{n+m} = W_{n}W_{m} − P_{2}U_{n}U_{m} − (P_{2} + 4Q)X_{n}X_{m} − P_{1}P_{1}(X_{n}Y_{m} + X_{m}Y_{n})

− P_{2}(P_{1}^{2} − P_{2} − 4Q)Y_{n}Y_{m}

and

2U_{n+m} = U_{n}W_{m} + U_{m}W_{n} + P_{1}(U_{n}U_{m} + X_{n}X_{m}) + (P_{1}^{2} − P_{2} − 4Q)(X_{n}Y_{m} + X_{m}Y_{n})

+ P_{1}(P_{1}^{2} − 2P_{2} − 4Q)Y_{n}Y_{m}.

Once again, using (11), we derive

2U_{n+m} = U_{n}W_{m} + U_{m}W_{n} + P_{1}(U_{n}U_{m} + A_{n}A_{m}) − L(A_{n}Y_{m} + Y_{n}A_{m}) + IY_{n}Y_{m},  (21)

where L = A_{2}P_{1} − (P_{1}^{2} − P_{2} − 4Q). Note the following easily established connection between I, J, K and L:

JL + K = A_{2}I.  (22)

If we put m = n in (20) we get

A_{2n} = A_{n}(W_{n} + A_{2}U_{n}) − JU_{n}Y_{n}.  (23)

Also, from [10] we have

U_{2n} = 2U_{n}W_{n} + P_{1}U_{n}^{2}  (24)
= P_{1}A_{n}^{2} − 2LA_{n}Y_{n} + IY_{n}^{2}.  (25)

Since

\frac{α_{i}^{n+m} − β_{i}^{n+m}}{α_{i} − β_{i}} = (α_{i}^{m} + β_{i}^{m}) (\frac{α_{i}^{n} − β_{i}^{n}}{α_{i} − β_{i}} ) − Q^{m} (\frac{α_{i}^{n−m} − β_{i}^{n−m}}{α_{i} − β_{i}} ) ,

we have

X_{n+m} + ρ_{i}Y_{n+m} = (W_{m} + ρ_{i}U_{m})(X_{n} + ρ_{i}Y_{n}) − Q^{m}(X_{n−m} + ρ_{i}Y_{n−m})

and we find

X_{n+m} = W_{m}X_{n} − P_{2}U_{m}Y_{n} − Q^{m}X_{n−m},
Y_{n+m} = U_{m}X_{n} + W_{m}Y_{n} + P_{1}U_{m}Y_{n} − Q^{m}Y_{n−m}.

It follows from the above and (11)

A_{n+m} = A_{n}(W_{m} + A_{2}U_{m}) − JU_{m}Y_{n} − Q^{m}A_{n−m},  (26)
Y_{n+m} = U_{m}A_{n} + Y_{n}(W_{m} + (P_{1} − A_{2})U_{m}) − Q^{m}Y_{n−m}.  (27)

Since (A_{n}) is odd, we have Q^{m}A_{n−m} = −Q^{n}A_{m−n} and

A_{n+m} = A_{n}(W_{m} + A_{2}U_{m}) − JU_{m}Y_{n} + Q^{n}A_{m−n}.  (28)

Putting m = kn and n = n in (28), we get

A_{(k+1)n} = A_{n}(W_{kn} + A_{2}U_{kn}) − JU_{kn}Y_{n} + Q^{n}A_{(k−1)n}.  (29)

We are now able to prove the main result of this section.

Theorem 13. If (A_{n}) is an odd recurrence sequence of order 4, then (A_{n}) is a divisibility sequence if and only if A_{n} | JU_{n}Y_{n} for all n ≥ 1.

Proof. If (A_{n}) is a divisibility sequence, then A_{n} | A_{2n} which implies A_{n} | JU_{n}Y_{n} by (23). Next, suppose that A_{n} | JU_{n}Y_{n}. Since it is well known (see [10]) that (U_{n}) is a divisibility sequence, we know that U_{n} | U_{kn} for any k ≥ 0. Thus, by (29) we have

A_{(k+1)n} ≡ Q^{n}A_{(k−1)n} (mod A_{n}) (k ≥ 1).

Hence, if A_{n} | A_{(k−1)n}, then A_{n} | A_{(k+1)n}. Since A_{n} | A_{n} and, by (23), A_{n} | A_{2n}, we find by induction that A_{n} | A_{mn} for any m ≥ 0.

Corollary 14. If (A_{n}) is an odd LDS of order 4, then A_{2} | P_{1}P_{2}.

Proof. Follows easily from the theorem and the simple fact that J ≡ P_{2} (mod A_{2}).

3 Monoapparitic primes in odd divisibility sequences of order 4

We now let (A_{n}) denote an odd, non-null, and non-degerate LDS of order 4. The purpose of much of this section is to identify certain monoapparitic primes in (A_{n}). If all primes are monoapparitic in (A_{n}), we say that (A_{n}) is monoapparitic. We observe by attempting all possible values for P_{1}, P_{2}, Q, A_{2} modulo 2 that only in the case of 2 | P_{1}, 2 ∤ P_{2}Q, 2 | A_{2} is it possible for 2 to not be monoapparitic in (A_{n}). In this case we see that 2 | I, where I is given by (17), ω_{1} = 2 and ω_{2} = 3.

We begin with the simple result below.

Proposition 15. If m is a positive integer and m | J, where J = A_{2}^{2} − P_{1}A_{2} + P_{2}, then A_{n} ≡ u_{n}(A_{2}, Q) (mod m).

Proof. We have A_{0} = 0 = u_{0}(A_{2}, Q), A_{1} = 1 = u_{1}(A_{2}, Q), A_{2} = u_{2}(A_{2}, Q), A_{3} = X_{3}+A_{2}Y_{3} = P_{1}A_{2} − P_{2} − Q ≡ A_{2}^{2} − Q = u_{3}(A_{2}, Q) (mod m). Also, since

Qu_{k}(A_{2}, Q) = A_{2}u_{k+1}(A_{2}, Q) − u_{k+2}(A_{2}, Q),

we get

Qu_{k+1} = A_{2}u_{k+2} − u_{k+3}, Q^{2}u_{k} = QA_{2}u_{k+1} − Qu_{k+2} = (A_{2}^{2} − Q)u_{k+2} − A_{2}u_{k+3}.

Here we use u_{k} to denote u_{k}(A_{2}, Q). It follows that

P_{1}Qu_{k+1} − Q^{2}u_{k} = (P_{1}A_{2} − A_{2}^{2} + Q)u_{k+2} − (P_{1} − A_{2})u_{k+3}.  (30)

Now suppose for some k ≥ 0, we have A_{k+i} ≡ u_{k+i}(A_{2}, Q) (mod m) (i = 0, 1, 2, 3); this is certainly true for k = 0. By (3), we get

A_{k+4} ≡ P_{1}u_{k+3} − (P_{2} + 2Q)u_{k+2} + P_{1}Qu_{k+1} − Q^{2}u_{k}
= P_{1}u_{k+3} − (P_{2} + 2Q)u_{k+2} + (P_{1}A_{2} − A_{2}^{2} + Q)u_{k+2} − (P_{1} − A_{2})u_{k+3}
= A_{2}u_{k+3} − (P_{2} + 2Q − P_{1}A_{2} + A_{2}^{2} − Q)u_{k+2}
≡ A_{2}u_{k+3} − Qu_{k+2} = u_{k+4} (mod m),

by (30) and J = A_{2}^{2} − P_{1}A_{2} + P_{2} ≡ 0 (mod m). The result now follows by induction.

Corollary 16. If p | J, then p is monoapparitic in (A_{n}).

Proof. If p | J, then by Proposition 15 we have A_{n} ≡ u_{n}(A_{2}, Q) (mod p). We must have p a monoapparitic prime in (A_{n}) because (u_{n}(A_{2}, Q)) has at most one rank of appearance modulo p.

We next turn to the problem of p | Q. We see that from (3) that each of (X_{n}), (Y_{n}) and (U_{n}) satisfies

T_{n+2} ≡ P_{1}T_{n+1} − P_{2}T_{n} (mod p) (n ≥ 2).

By the initial conditions for (X_{n}), (Y_{n}) and (U_{n}) and mathematical induction, it is easy to show that

Y_{n} ≡ u_{n−1}(P_{1}, P_{2}) (mod p) (n ≥ 1),
X_{n} ≡ −P_{2}u_{n−2}(P_{1}, P_{2}) (mod p) (n ≥ 2),
U_{n} ≡ u_{n}(P_{1}, P_{2}) (mod p) (n ≥ 0).

It follows that

A_{n} = X_{n} + A_{2}Y_{n} ≡ A_{2}u_{n−1} − P_{2}u_{n−2} (mod p) (n ≥ 2),

where we now use u_{n} to denote u_{n}(P_{1}, P_{2}). Observe that since u_{n−1}^{2} − u_{n−2}u_{n} = P_{2}^{2}, we must have p | P_{2} if p | gcd(u_{n}, u_{n−1}) or p | gcd(u_{n−1}, u_{n−2}). However, when p | P_{2}, it is easy to show that u_{n} ≡ P_{1}^{n−1} (mod p); hence p | P_{1}, which since gcd(P_{1}, P_{2}, Q) = 1, is impossible. Thus, gcd(u_{n}, u_{n−1}) = 1 and gcd(P_{2}, u_{n}) = 1 for all n ≥ 1, when p | Q. We can now prove the following proposition.

Proposition 17. If p be a prime such that p | Q, then p must be monoapparitic in (A_{n}).

Proof. By Theorem 13, we must have A_{n} | JY_{n}U_{n} for all n ≥ 1. If p | A_{n}, then p | J means that p is monoapparitic in (A_{n}). If p ∤ JY_{n}, then p | U_{n} which means that p | u_{n}(P_{1}, P_{2}) and

P_{1}u_{n−1} − P_{2}u_{n−2} ≡ 0 (mod p).

Also, p | A_{n} implies that

A_{2}u_{n−1} − P_{2}u_{n−2} ≡ 0 (mod p).

Hence, p | (A_{2} − P_{1})u_{n−1}. Since, p ∤ u_{n−1}, we get p | A_{2} − P_{1}, but in this case we get A_{n} ≡ u_{n}(P_{1}, P_{2}) (mod p), which means that p is monoapparitic in (A_{n}). If p | Y_{n}, then p | u_{n−1}, which since p | A_{n} means that p | P_{2}u_{n−2}. If p ∤ P_{2}, then p | u_{n−2}, which is impossible. If p | P_{2}, then p | gcd(P_{2}, u_{n−1}) and gcd(u_{n−1}, u_{n}) ≠ 1, which is also impossible.

We next define two sequences (G_{n}) and (H_{n}):

G_{n} = gcd(A_{n}, Y_{n}) and H_{n} = gcd(A_{n}, U_{n}).

Note that since A_{n} = X_{n} + A_{2}Y_{n}, we have G_{n} = gcd(X_{n}, Y_{n}). By [9, Lemma 10.3.8], we know that (G_{n}) is a divisibility sequence, but not necessarily a LDS.

Proposition 18. For G_{n} and H_{n} defined as above, we have gcd(G_{n}, Q) = 1. Also, gcd(H_{n}, Q) = 1 when gcd(A_{2} − P_{1}, Q) = 1

Proof. The first result follows from [9, Lemma 10.3.9]. Next, suppose that p is any prime such that p | Q and p | H_{n}. Referring to the proof of Proposition 17, we find that we must have p | A_{2} − P_{1}, which means that gcd(A_{2} − P_{1}, Q) ≠ 1.

If p is any prime, let ρ = ρ(p) denote the least positive integer value of n (if it exists) such that p | G_{n}.

Theorem 19. If p is any prime such that p | G_{n}, then ρ | n.

Proof. This proof can be found in [9, Theorem 10.3.13].

We will next obtain a somewhat similar result for (H_{n}). By making use of the identity

α_{i}^{n+m} + β_{i}^{n+m} = (α_{i}^{n} + β_{i}^{n})(α_{i}^{m} + β_{i}^{m}) − Q^{m}(α_{i}^{n−m} + β_{i}^{n−m}),

we can easily derive

W_{m+n} = W_{m}W_{n} − P_{2}U_{m}U_{n} − Q^{m}W_{n−m},
U_{m+n} = W_{m}U_{n} + W_{n}U_{m} + P_{1}U_{n}U_{m} − Q^{m}U_{n−m}.  (31)

From (23) and (24), we see that H_{n} | H_{2n}.

By (31) and (29), we have

U_{(k+1)n} = W_{kn}U_{n} + W_{n}U_{kn} + P_{1}U_{kn}U_{n} − Q^{n}U_{(k−1)n},
A_{(k+1)n} = A_{n}(W_{kn} + A_{2}U_{kn}) − JU_{kn}Y_{n} + Q^{n}A_{(k−1)n}.

Since H_{n} | H_{n} and H_{n} | H_{2n}, it is easy to establish by induction on m that H_{n} | H_{mn}; thus, (H_{n}) is a divisibility sequence.

For any fixed prime p, let σ = σ(p), if it exists, be the least positive value of n such that p | H_{n}. If p | Q and p | H_{n}, then as we have seen earlier p | u_{n}(P_{1}, P_{2}) and A_{n} ≡ U_{n} ≡ u_{n}(P_{1}, P_{2}) (mod p) (p | Q). Thus, if p | H_{n}, then σ | n. We next show that if p is any odd prime such that p ∤ Q, then σ | n whenever p | H_{n}.

Theorem 20. Let p be any odd prime such that p ∤ Q. If p | H_{n}, then σ(p) | n.

Proof. We first note that by (15) we have H_{n} | IY_{n}^{2} for any n. Suppose p | H_{n} and n = qσ +r with 0 < r < σ. From (21) and (20) we have

2U_{n} = U_{qσ}W_{r} + W_{qσ}U_{r} + P_{1}(U_{qσ}U_{r} + A_{qσ}A_{r}) − L(A_{qσ}Y_{r} + Y_{qσ}A_{r}) + IY_{qσ}Y_{r}

and

2A_{n} = W_{qσ}A_{r} + A_{qσ}W_{r} + A_{2}(U_{qσ}A_{r} + A_{qσ}U_{r}) − J(U_{qσ}Y_{r} + Y_{qσ}U_{r}).

Since (H_{n}) is a divisibility sequence and p | H_{σ} (σ = σ(p)) we must have p | H_{qσ} and p | IY_{qσ}. Thus,

0 ≡ W_{qσ}U_{r} − LY_{qσ}A_{r} (mod p),
0 ≡ W_{qσ}A_{r} − JY_{qσ}U_{r} (mod p).

If p ∤ I, then p | Y_{qσ}, p | W_{qσ}U_{r} and p | W_{qσ}A_{r}; consequently if p ∤ W_{qσ}, we get p | H_{r}. If p | W_{qσ}, then by (16) we get p | 4Q^{qσ}, which is impossible by selection of p. If p | I, then by (22) and (16), we get

W_{qσ}^{2} − LJY_{qσ}^{2} ≡ W_{qσ}^{2} + KY_{qσ}^{2} ≡ 4Q^{qσ} (mod p).

Since p ∤ 4Q^{qσ}, we must also have p | H_{r}. In either case we find that we get a contradiction to the definition of σ when r > 0. Hence, σ(p) | n.

We next address the question of the existence of ρ(p) and σ(p). We will only concern ourselves with those primes p such that p divides some term A_{n} (n > 0) of (A_{n}) and p ∤ J. By Theorem 13, we must have p | G_{n} or p | H_{n}; thus, at least one of ρ(p) or σ(p) must exist. From (23) and (25), we can easily deduce that

G_{n} | H_{2n};  (32)

hence, if ρ(p) exists, then p | H_{2ρ} and therefore σ(p) must exist. Also, even if ρ(p) does not exist, then σ(p) must exist and p is monoapparitic in (A_{n}). Since gcd(G_{n}, Q) = 1, we see that if p | Q, then ρ(p) cannot exist. Also, if p | Q and A_{2} ≢ P_{1} (mod p), then p ∤ H_{n} and as a result σ(p) cannot exist.

We will now examine several additional special cases. Throughout this discussion p will denote a prime such that p ∤ 2Q.

Case 1: p | P_{1}.

In this case, it is easy to prove by using (3) and mathematical induction that for n ≥ 0 we have

X_{2n} ≡ 0, X_{2n+1} ≡ ū_{n}(−P_{2}, Q), Y_{2n} ≡ ū_{2n}(−P_{2}, Q), Y_{2n+1} ≡ 0 (mod p).  (33)

Hence, G_{n} = gcd(X_{n}, Y_{n}) ≡ ū_{n}(−P_{2}, Q) (mod p). By results in [4] (See §4 below for details.) we know that if p ∤ P_{2}, then p | ū_{n}(−P_{2}, Q) if and only if τ | n, where τ is the rank of appearance of p in (ū_{n}(−P_{2}, Q)). Since p ∤ Q, τ must exist and τ | p − κ, where κ is the value of the Legendre symbol ((P_{2}^{2} + 4QP_{2})/p). Hence, ρ(p) exists and ρ(p) = τ when p ∤ P_{2}. Suppose p | P_{2}; then p ∤ ū_{n}(−P_{2}, Q) for any odd n > 0 and ρ(p) does not exist. If 2 | n, then p | (ū_{n}(−P_{2}, Q)) if and only if p | n; hence, ρ(p) = τ = p in this case.

Proposition 21. If p | P_{1}, then p is monoapparitic in (A_{n}) when p ∤ A_{2}. If p | P_{1}, p | A_{2} and 2 | τ, then p is also monoapparitic in (A_{n}). If p | P_{1}, p | A_{2} and 2 ∤ τ, it is possible for p to have two ranks of appearance in (A_{n}), namely 2 and τ. Also, if p | P_{1}, p | A_{2} and p | P_{2}, then p is monoapparitic in (A_{n}).

Proof. If p | P_{1}, p | A_{2} and p | P_{2}, then p | J and therefore p is monoapparitic in (A_{n}) by Corollary 16. Furthermore, by (33) we have

A_{n} = \begin{cases}ū_{n}(−P_{2}, Q), & if 2 ∤ n; \\ A_{2}ū_{n}(−P_{2}, Q), & if 2 | n. \end{cases}

The result now easily follows from our observations in Case 1.

Case 2: p ∤ P_{1}, p | Δ.

In [10, §6] it is shown that

U_{n} ≡ nu_{n}(P_{1}/2, Q) (mod p).

Also, it is easy, on using the initial conditions for (X_{n}) and (Y_{n}), to see that

X_{n} + (P_{1}/2)Y_{n} ≡ u_{n}(P_{1}/2, Q) (mod p)  (34)

for n = 0, 1, 2, 3. On putting P_{2} ≡ P_{1}^{2}/4 (mod p), we use (3) and mathematical induction to verify that (34) is true for all n ≥ 1. Thus, if p | G_{n}, then p | H_{n}. Hence, if ρ(p) exists, then σ(p) exists and σ(p) | ρ(p) by Theorem 20.

Case 3: p ∤ P_{1}Δ, p | E.

We first observe by [12, (2.5)] we have

ΔP_{1}^{2} + 4E = (P_{1}^{2} − 2P_{2} − 8Q)^{2};  (35)

thus, since p | E and p ∤ P_{1}Δ, we must have (Δ/p) = 1. Let 𝕂 be the splitting field of F (x) in 𝔽_{p}[x] and let α_{1}, β_{1}, α_{2}, β_{2} (α_{1}β_{1} = α_{2}β_{2} = Q) be the roots of F (x) = 0 in 𝕂. Since E = (α_{1} − β_{1})^{2}(α_{2} − β_{2})^{2}, we have α_{1} = β_{1} or α_{2} = β_{2} in 𝕂. We assume with no loss of generality that α_{1} = β_{1}. If, as well, α_{2} = β_{2}, then since (α_{i} − β_{i})^{2} = ρ_{i}^{2} − 4Q (i = 1, 2), we see that ρ_{1}^{2} = ρ_{2}^{2}, which since p ∤ P_{1}Δ is impossible. Thus α_{1} = β_{1} and α_{2} ≠ β_{2}. Also, since (Δ/p) = 1, we must have ρ_{1} − ρ_{2} ∈ 𝔽_{p} ⊆ 𝕂 and therefore ρ_{1}, ρ_{2} ∈ 𝔽_{p}. Since α_{1} = β_{1}, we have ρ_{1} = 2α_{1}. Thus in 𝔽_{p}

u_{n}(ρ_{1}, Q) = \frac{α_{1}^{n} − β_{1}^{n}}{α_{1} − β_{1}} = nα_{1}^{n−1} and u_{n}(ρ_{2}, Q) = \frac{α_{2}^{n} − β_{2}^{n}}{α_{2} − β_{2}} .

By definition of (X_{n}) and (Y_{n}), we find that in 𝔽_{p}

X_{n} + ρ_{1}Y_{n} = nα_{1}^{n−1} and X_{n} + ρ_{2}Y_{n} = u_{n}(ρ_{2}, Q).

Thus, if p | G_{n}, then nα_{1}^{n−1} = 0 and u_{n}(ρ_{2}, Q) = 0 in 𝔽_{p}. Since p ∤ Q, we see that p | n. Also, by [10, Lemma 8.1] we know that if τ is the rank of appearance of p in u_{n}(ρ_{2}, Q), then τ | n, where τ | p − λ and λ is the value of the Legendre symbol ((P_{1}^{2} − 2P_{2} − 8Q)/p). Since α_{2} ≠ β_{2}, we cannot have λ = 0; thus, gcd(τ, p) = 1 and pτ | n. Furthermore, if pτ | n, then X_{n} + ρ_{1}Y_{n} = X_{n} + ρ_{2}Y_{n} in 𝔽_{p}. Since ρ_{1} − ρ_{2} ≠ 0, Y_{n} = X_{n} = 0 and p | G_{n}. It follows that in this case, ρ(p) exists and ρ(p) = pτ.

Finally, we deal with the case of p ∤ ΔEQ. If (Δ/p) = 1, there must exist some d such that d^{2} ≡ Δ (mod p). In this case, put e = P_{1}^{2} − Δ − 16Q + 2P_{1}d and η is the value of the Legendre symbol (e/p). We define the function Φ(p) by

Φ(p) = \begin{cases}p − η, & if (Δ/p) = 1, (E/p) = 1; \\ p^{2} − 1, & if (Δ/p) = 1, (E/p) = −1; \\ p^{2} − (E/p), & if (Δ/p) = −1. \end{cases}

We now have the following result.

Theorem 22. If p is any odd prime such that p ∤ ΔEQ, then both ρ = ρ(p) and σ = σ(p) must exist and are divisors of Φ(p).

Proof. By [9, Theorem 10.3.10] and results in [10, §7], we know that p | G_{Φ(p)} and p | U_{Φ(p)}; hence p | H_{Φ(p)}. It follows that both ρ and σ exist for p and by Theorems 19 and 20, we must have ρ(p) | Φ(p) and σ(p) | Φ(p), respectively.

While it is the case that the Lucas sequences have a single rank of appearance, we have seen that higher order divisibility sequences may have multiple ranks of appearance [8]. In the theorem below we now show that (A_{n}) can have at most two ranks of appearance for any prime p.

Theorem 23. Any prime p can have at most two ranks of appearance in (A_{n}).

Proof. By our previous results we may assume that p ∤ 2QJ. If p | A_{n}, then by Theorem 13, we must have p | Y_{n} or p | U_{n}. That is, ρ(p) | n or σ(p) | n. It follows that there can be at most two ranks of appearance of p in (A_{n}), namely ρ and σ.

We will next derive some simple conditions under which a prime p must be monoapparitic in (A_{n}). We have already seen that this will be the case if p | Q or p | J; thus we will assume in what follows that p ∤ 2QJ. Let ω = ω_{1}(p), where ω_{1} is defined in Definition 10 with (T_{n}) = (A_{n}). Put ρ = ρ(p), σ = σ(p), when they exist. Since p | A_{ρ} and p | A_{σ}, it is clear that ω ≤ ρ and ω ≤ σ.

Proposition 24. For the symbols p, ω, σ and ρ defined above, we have ω = ρ or ω = σ.

Proof. By Theorems 23, 19 and 20, we must have ρ | ω or σ | ω. Since ρ, σ ≥ ω, we can only have ω = ρ or ω = σ.

Proposition 25. Under the conditions of Proposition 24, p is monoapparitic in (A_{n}) when σ | ρ or ρ | σ.

Proof. We show that if p | A_{n}, then ω | n. Suppose σ | ρ. In this case σ ≤ ρ; hence, by Proposition 24 and the definition of ω we must have ω = σ. If p | A_{n}, then we must have σ | n or ρ | n by Theorem 23, which means that σ | n and ω | n. Similarly, if ρ | σ, then ω = ρ and ρ | n.

Proposition 26. If p ∤ P_{1}, and p | Δ, then p is monoapparitic in (A_{n}).

Proof. In Case 2 we showed that if p satisfies the conditions of the proposition, then either ρ(p) and σ(p) both exist and σ | ρ, or ρ(p) does not exist. In either case p must be monoapparitic in (A_{n}).

By (32) we see that if p | G_{ρ}, we must have p | H_{2ρ} and therefore

σ | 2ρ

by Theorem 20. It follows that if 2 ∤ σ, then σ | ρ and p is monoapparitic in (A_{n}).

Proposition 27. If ρ ≤ σ, then p is monoapparitic in (A_{n}).

Proof. We may assume that 2 | σ. Since σ/2 | ρ, we get ρ = tσ/2 ≤ σ. Thus, t = 1, 2. If t = 2, then ρ = σ and we are done. If t = 2, then ρ = σ/2. Since ρ | σ, the result follows from Proposition 25.

Thus, if ρ ≤ σ or 2 ∤ σ, we see that p is monoapparitic in (A_{n}). In the following result we present another condition for this to be the case.

Theorem 28. If p ∤ I, then (A_{n}) has a single rank of appearance modulo p.

Proof. We may assume that p ∤ 2QJ. It suffices to show that if p | A_{n}, then ω | n. If p | A_{n}, then p | U_{n} or p | Y_{n} which means that p | H_{n} or p | G_{n}. If p | H_{n}, by (15) we see that p | G_{n}. Thus, p | G_{ω} and we must have ρ | ω. Since ω ≤ ρ, we have ω = ρ. Also, since p | G_{n}, we have ρ | n, which means that ω | n.

We have seen, then, that if p ∤ I, p is a monoapparitic prime in (A_{n}). If I ≠ 0, this means that only a finite number of primes can have two ranks of appearance in (A_{n}). In the next section we will deal with the case of I = 0 and the case of p | I.

4 Some results when I = 0 or p | I

Put

g = P_{1}^{2} − P_{2} − 4Q, h = P_{1}(P_{1}^{2} − 2P_{2} − 4Q)  (36)

and note that

E = g^{2} − P_{1}h.  (37)

If I = 0, we have from (17) that

P_{1}A_{2}^{2} − 2gA_{2} + h = 0.  (38)

As mentioned in Section 1, we assume that P_{1} ≠ 0. By (37) the discriminant of

P_{1}x^{2} − 2gx + h = 0

is 4E. Thus, for A_{2} ∈ ℤ, we see that E must be a perfect integral square, which means that G = 1.

In the case of p | I, we can convert (38) into a congruence modulo p and find that

(P_{1}A_{2} − g)^{2} ≡ E (mod p).  (39)

We are now able to complete our discussion of the special cases that arise when p | D in (4).

Proposition 29. If p ∤ 2P_{1} and p | E, then p is monoapparitic in (A_{n}).

Proof. Put

q ≡ (P_{2} + 4Q)/P_{1} (mod p).

Since p | E, we have

q^{2} ≡ 4Q (mod p).

by the second formula in (5). From (39), we see that

A_{2} ≡ P_{1} − q (mod p);

thus,

J = A_{2}^{2} − P_{1}A_{2} + P_{2} ≡ q^{2} − P_{1}q + P_{2} ≡ 4Q − (P_{2} + 4Q) + P_{2} ≡ 0 (mod p).

By Corollary 16, p must be monoapparitic in (A_{n}). By combining the results of Propositions 17, 26 and 29, we have the following result. Theorem 30. If p is any prime such that p ∤ 2P_{1} and p | ΔEQ, then p is monoapparitic in (A_{n}).

We next deal with (A_{n}) when p is an odd prime and Case (i) of Section 1 holds, i.e., G = S ≠ 1. We put

d = P_{1}^{2} − 2P_{2} − 8Q, c = P_{1}(P_{1}^{2} − 3P_{2} − 4Q).  (40)

By [12, Theorem 5.2] we know that if (A_{n}) is an odd LDS, then

dA_{2} = c ± \sqrt{ΔE};  (41)

thus,

d^{2}A_{2}^{2} − 2cdA_{2} + c^{2} − ΔE = 0.  (42)

In what follows we will assume that p ∤ P_{1}. Since p | I, by (38) we have

P_{1}A_{2}^{2} − 2gA_{2} + h ≡ 0 (mod p).  (43)

It is easy to verify by referring to (5), (36) and (40) that

gd − P_{1}c = 2E  (44)

and

ΔP_{1}h + P_{1}^{2}E = c^{2}.  (45)

From (42) and (43), we have

P_{1}d^{2}A_{2}^{2} − 2cdP_{1}A_{2} + P_{1}(c^{2} − ΔE) ≡ 0 (mod p)

and

P_{1}d^{2}A_{2}^{2} − 2gd^{2}A_{2} + d^{2}h ≡ 0 (mod p).

On subtracting the second of these congruences from the first we get

2d(gd − P_{1}c)A_{2} + P_{1}(c^{2} − ΔE) − d^{2}h ≡ 0 (mod p).  (46)

Now by (45) we have

P_{1}(c^{2} − ΔE) − d^{2}h = E(P_{1}^{3} − P_{1}Δ − 4h) = −4E(h − P_{1}P_{2}) = 4Ec;

it follows from this, (46) and (44) that

4dEA_{2} − 4Ec ≡ 0 (mod p).  (47)

We are now able to derive the following simple result.

Theorem 31. If p is a prime such that p ∤ 2P_{1}, then p is monoapparitic in (A_{n}) when S = G ≠ 1.

Proof. By Theorem 30, we see that the theorem holds when p | ΔE. Suppose p ∤ ΔE and p | I. If p = 2 and p ∤ P_{1}, then we have already seen that p is monoapparitic in (A_{n}). Thus, we may assume here that p ≠ 2. By (47), we get

dA_{2} − c ≡ 0 (mod p)

and by (41) we must have p | ΔE, a contradiction. Thus p must be monoapparitic in (A_{n}).

In [11], it is shown that if G = 1, there must exist integers r_{1}, r_{2}, q_{1}, q_{2} such that r_{1}, r_{2} > 0; gcd(r_{1}, q_{1}) = gcd(r_{2}, q_{2}) = 1;

P_{1}^{2} = r_{1}r_{2}, P_{2} = q_{1}r_{2} + q_{2}r_{1} − 4q_{1}q_{2}, Q = q_{1}q_{2}.  (48)

We find that Δ = P_{1}^{2} − 4P_{2} = d_{1}d_{2}, where d_{i} = r_{i} − 4q_{i} (i = 1, 2), E = (q_{1}r_{2} − q_{2}r_{1})^{2} and g = r_{1}r_{2} − r_{1}q_{2} − r_{2}q_{1}. It is also shown in [11] that for the values of P_{1}, P_{2}, Q given by (48), we have

α_{1} = μ_{1}μ_{2}, β_{1} = ν_{1}ν_{2}, α_{2} = ν_{1}μ_{2}, β_{2} = μ_{1}ν_{2},

where μ_{i} + ν_{i} = \sqrt{r_{i}}, μ_{i}ν_{i} = q_{i} (i = 1, 2). Since μ_{1}/ν_{1} = α_{1}/α_{2} and μ_{2}/ν_{2} = α_{2}/β_{1}, we see that since (A_{n}) is non-degenerate, we cannot have μ_{1}/ν_{1} or μ_{2}/ν_{2} a root of unity; in particular μ_{1} ≠ ν_{1} and μ_{2} ≠ ν_{2}.

We next observe that

(α_{1}^{n} − β_{1}^{n}) + (α_{2}^{n} − β_{2}^{n}) = μ_{1}^{n}μ_{2}^{n} − ν_{1}^{n}ν_{2}^{n} + μ_{1}^{n}ν_{2}^{n} − μ_{2}^{n}ν_{1}^{n} = (μ_{1}^{n} − ν_{1}^{n})(μ_{2}^{n} + ν_{2}^{n})  (49)
(α_{1}^{n} − β_{1}^{n}) − (α_{2}^{n} − β_{2}^{n}) = (μ_{1}^{n} + ν_{1}^{n})(μ_{2}^{n} − ν_{2}^{n}).  (50)

Put

M_{n} = u_{n}(\sqrt{r_{1}}, q_{1})v_{n}(\sqrt{r_{2}}, q_{2}), N_{n} = v_{n}(\sqrt{r_{1}}, q_{1})u_{n}(\sqrt{r_{2}}, q_{2}).

We have

(μ_{1}^{n} − ν_{1}^{n})(μ_{2}^{n} + ν_{2}^{n}) = (μ_{1} − ν_{1})M_{n}, (μ_{1}^{n} + ν_{1}^{n})(μ_{2}^{n} − ν_{2}^{n}) = (μ_{2} − ν_{2})N_{n}.

Also, by (49) and (50) and the definition of (X_{n}), (Y_{n}), we get

(α_{1} − β_{1})X_{n} + (α_{1} − β_{1})ρ_{1}Y_{n} + (α_{2} − β_{2})X_{n} + (α_{2} − β_{2})ρ_{2}Y_{n} = (μ_{1} − ν_{1})M_{n}, (α_{1} − β_{1})X_{n} + (α_{1} − β_{1})ρ_{1}Y_{n} − (α_{2} − β_{2})X_{n} − (α_{2} − β_{2})ρ_{2}Y_{n} = (μ_{2} − ν_{2})N_{n}.

Since ρ_{i} = α_{i} + β_{i} (i = 1, 2), we see, by (49) and (50) with n = 2, that

(α_{1} − β_{1})ρ_{1} + (α_{2} − β_{2})ρ_{2} = (μ_{1}^{2} − ν_{1}^{2})(μ_{2}^{2} + ν_{2}^{2})

and

(α_{1} − β_{1})ρ_{1} − (α_{2} − β_{2})ρ_{2} = (μ_{1}^{2} + ν_{1}^{2})(μ_{2}^{2} − ν_{2}^{2}).

It follows that

\sqrt{r_{2}}X_{n} + \sqrt{r_{1}}(r_{2} − 2q_{2})Y_{n} = M_{n},  (51)
\sqrt{r_{1}}X_{n} + \sqrt{r_{2}}(r_{1} − 2q_{1})Y_{n} = N_{n}.  (52)

From [11], we also have

U_{n} = u_{n}(\sqrt{r_{1}}, q_{1})u_{n}(\sqrt{r_{2}}, q_{2}).

If we put

R_{n} = ū_{n}(r_{1}, q_{1})v̄_{n}(r_{2}, q_{2}), S_{n} = ū_{n}(r_{2}, q_{2})v̄_{n}(r_{1}, q_{1}),

we get

M_{n} = \sqrt{r_{2}}R_{n}, N_{n} = \sqrt{r_{1}}S_{n} if 2 ∤ n,
M_{n} = \sqrt{r_{1}}R_{n}, N_{n} = \sqrt{r_{2}}S_{n} if 2 | n,

and

U_{n} = \begin{cases}ū_{n}(r_{1}, q_{1})ū_{n}(r_{2}, q_{2}), & if 2 ∤ n; \\ P_{1}ū_{n}(r_{1}, q_{1})ū_{n}(r_{2}, q_{2}), & if 2 | n. \end{cases}  (53)

If I = 0, then with a possible interchange of the parameters r_{1}, r_{2} and q_{1}, q_{2}, we get

A_{2} = \frac{g ± \sqrt{E}}{P_{1}} = \sqrt{r_{1}r_{2}} − 2q_{1}\sqrt{\frac{r_{2}}{r_{1}}} = v_{2}(\sqrt{r_{1}}, q_{1})\frac{u_{2}(\sqrt{r_{2}}, q_{2})}{\sqrt{r_{1}}}.

Notice that

A_{−1} = \frac{−1}{Q} = v_{−1}(\sqrt{r_{1}}, q_{1})\frac{u_{−1}(\sqrt{r_{2}}, q_{2})}{\sqrt{r_{1}}},

A_{0} = 0 = v_{0}(\sqrt{r_{1}}, q_{1})\frac{u_{0}(\sqrt{r_{2}}, q_{2})}{\sqrt{r_{1}}},

A_{1} = 1 = v_{1}(\sqrt{r_{1}}, q_{1})\frac{u_{1}(\sqrt{r_{2}}, q_{2})}{\sqrt{r_{1}}};

thus, if we put

B_{n} = v_{n}(\sqrt{r_{1}}, q_{1})\frac{u_{n}(\sqrt{r_{2}}, q_{2})}{\sqrt{r_{1}}} = N_{n}/\sqrt{r_{1}},

we have A_{i} = B_{i} (i = −1, 0, 1, 2). Since α_{1}, β_{1}, α_{2}, β_{2} are the distinct roots of (2), we see that the sequence (B_{n}) given by

B_{n} = (\frac{μ_{1}^{n} + ν_{1}^{n}}{μ_{1} + ν_{1}} ) (\frac{μ_{2}^{n} − ν_{2}^{n}}{μ_{1} − ν_{1}} ) = \frac{α_{1}^{n} − β_{1}^{n} + α_{2}^{n} − β_{2}^{n}}{α_{1} − β_{1} + α_{2} − β_{2}}

must satisfy (3). Since the initial values of (B_{n}) and (A_{n}) are equal, it follows that

A_{n} = B_{n} = v_{n}(\sqrt{r_{1}}, q_{1})\frac{u_{n}(\sqrt{r_{2}}, q_{2})}{\sqrt{r_{1}}} = \begin{cases}v̄_{n}(r_{1}, q_{1})ū_{n}(r_{2}, q_{2}), & if 2 ∤ n; \\ \frac{r_{2}}{P_{1}} v̄_{n}(r_{1}, q_{1})ū_{n}(r_{2}, q_{2}), & if 2 | n, \end{cases}  (54)

when I = 0. Also, if p ∤ P_{1}QE, G = 1 and p | I, we can use (39) and the above reasoning to show that

A_{n} ≡ \begin{cases}v̄_{n}(r_{1}, q_{1})ū_{n}(r_{2}, q_{2}) (mod p), & if 2 ∤ n; \\ \frac{r_{2}}{P_{1}} v̄_{n}(r_{1}, q_{1})ū_{n}(r_{2}, q_{2}) (mod p), & if 2 | n. \end{cases}  (55)

Thus, by Theorem 31 we have disposed of Case (i) in Section 1. Since in Case (ii), (A_{n}) is the Lucas sequence (u_{n}), we see that p must also be monoapparitc in (A_{n}). This leaves only the two cases when G = 1. We deal with the first of these in the next section.

5 The case of G = 1 and S ≠ 1

Before proceeding any further, we will need to review some simple properties of the Lehmer sequences (ū_{n}(r, q)) and (v̄_{n}(r, q)). We have the simple identities

ū_{2n} = v̄_{n}ū_{n}  (56)

and

\begin{cases}rv̄_{n}^{2} − dū_{n}^{2} = 4q^{n}, & if 2 ∤ n; \\ v̄_{n}^{2} − rdū_{n}^{2} = 4q^{n}, & if 2 | n. \end{cases}  (57)

where d = r − 4q and we use ū_{n} and v̄_{n} to represent ū_{n}(r, q) and v̄_{n}(r, q), respectively. If 2 ∤ n, it is easy to prove

ū_{n}(mr, mq) = m^{\frac{n−1}{2}} ū_{n}(r, q)  (58)

and

ū_{n}(r − 4q, q) = v̄_{n}(r, q).  (59)

Also, from results in [4] the sequence (ū_{n}(r, q)) is a fourth-order linear divisibility sequence as is (a_{n}ū_{n}(r, q)), where (a_{n}) is a special periodic sequence of integers such that a_{1} = 1 and a_{n} | a_{2n}. Indeed, the sequence (a_{n}) must be some (v̄_{n}(r, q)), where q = ±1 and r = q, 2q or 3q.

Let τ = τ(p) be the rank of appearance (apparition) of a prime p (p ∤ 2rq) in (ū_{n}(r, q)). Note that p | ū_{n} ⇔ τ | n ([4, Theorem 1.8]). We use ψ = ψ(p) to denote the least positive value of n, if it exists, such that p | v̄_{n}. We have two simple results.

Theorem 32. If p ∤ 2rq, then ψ exists if and only if 2 | τ; furthermore, if 2 | τ, then ψ = τ/2.

Proof. Suppose 2 | τ; by definition of τ we see that p ∤ ū_{τ/2} and by (56) p | v̄_{τ/2}. Thus, ψ exists and ψ ≤ τ/2. Also, by (56), we have p | ū_{2ψ} and therefore τ | 2ψ ⇒ τ/2 | ψ ⇒ ψ = τ/2. Next, assume that ψ exists; as above, we have τ | 2ψ. Also, by (57), we see that p ∤ ū_{ψ}; hence τ ∤ ψ ⇒ 2 | τ.

Theorem 33. If p ∤ 2rq and τ is even, then p | v_{n} ⇒ ψ | n. and 2 ∤ n/ψ.

Proof. We have ψ = τ/2 exists by Theorem 32. Suppose p | v̄_{n}. Since p | ū_{2n}, we have τ | 2n and τ ∤ n. Hence, ψ | n and since 2ψ ∤ n, n/ψ is odd.

It is shown in [12] that if G = 1 and S ≠ 1, then (A_{n}) is given by (54), where r_{1}, r_{2}, q_{1} must be perfect integral squares. Put r_{i} = s_{i}^{2} (i = 1, 2). We find that

A_{n} = v_{n}(s_{1}, q_{1})u_{n}(s_{2}, q_{2})/s_{1}  (60)

and if (A_{n}) is to be a divisibility sequence, we must have

v_{n}(s_{1}, q_{1}) | 2v_{n}(s_{2}, q_{2}) (for all n ≥ 0).  (61)

Let τ_{i} be the rank of appearance of the prime p (p ∤ q_{i}) in (u_{n}(s_{i}, q_{i})) (i = 1, 2) and put

ω = \begin{cases}τ_{1}/2, & if 2 | τ_{1}; \\ τ_{2}, & if 2 ∤ τ_{1}. \end{cases}

Note that for A_{n} given by (60), we have p | A_{ω}.

We now have the main result of this section.

Theorem 34. Let A_{n} be given by (60), subject to (61). If p ∤ 2Q and p | A_{n}, then ω | n.

Proof. If 2 ∤ τ_{1}, then by Theorem 32 p ∤ v_{n}(s_{1}, q_{1}) for any n. Thus by (60) we must have p | u_{n}(s_{2}, q_{2}) and τ_{2} | n. Suppose 2 | τ_{1}. If p | v_{n}(s_{1}, q_{1}), we must have τ_{1}/2 | n by Theorem 33. If p | u_{n}(s_{2}, q_{2}), then since, p | v_{τ_{1}/2}(s_{1}, q_{1}), we must have p | v_{τ_{1}/2}(s_{2}, q_{2}) by (61). Thus, since ψ_{2} must exist, we have 2 | τ_{2} and τ_{1}/2 | τ_{2}/2. It follows that since τ_{2} | n, we get τ_{1}/2 | n.

It follows from Proposition 17 and Theorem 34 that if G = 1, S ≠ 1 and p is an odd prime, then (A_{n}) must be monoapparitic modulo p. We have also shown that if I = 0 and S ≠ 1, the primes which can divide the terms of (A_{n}) must all, with the possible exception of p = 2, be monoapparitic.

6 The case of S = G = 1

We will first investigate the problem of determining those primes p which can be monoapparitic in (A_{n}) when all we know is just that G = 1. We may assume that p ∤ 2P_{1}Q and p | I. If p | U_{n} and p | A_{n}, then by (53) and (55) we have

p | ū_{n}(r_{1}, q_{1})ū_{n}(r_{2}, q_{2}) and p | v̄_{n}(r_{1}, q_{1})ū_{n}(r_{2}, q_{2}).

Let τ_{i} (i = 1, 2) be the rank of appearance (apparition) of p in ū_{n}(r_{i}, q_{i}). Since, by (57), p ∤ gcd(ū_{n}(r_{1}, q_{1}), v̄_{n}(r_{1}, q_{1})), we must have p | ū_{n}(r_{2}, q_{2}) and this holds if and only if τ_{2} | n. Thus, we must have σ = σ(p) = τ_{2}.

If p | A_{n} and p | Y_{n}, then p | X_{n}; also, by (51), (52) and (48), we must have, p | R_{n} and p | S_{n}. Hence,

p | ū_{n}(r_{1}, q_{1})v̄_{n}(r_{2}, q_{2}) and p | ū_{n}(r_{2}, q_{2})v̄_{n}(r_{1}, q_{1}).

If τ_{1} | n, then p | ū_{n}(r_{1}, q_{1}) and p ∤ v̄_{n}(r_{1}, q_{1}) by (57). Thus, τ_{2} | n and ρ = ρ(p) = lcm[τ_{1}, τ_{2}]. If τ_{1} ∤ n, then p | v̄_{n}(r_{2}, q_{2}). We must have 2 | τ_{2} and τ_{2}/2 | n. Also, p ∤ ū_{n}(r_{2}, q_{2}) and p | v̄_{n}(r_{1}, q_{1}) and we must also have 2 | τ_{1} and τ_{1}/2 | n. In this case we put ψ_{i} = τ_{i}/2 and let 2^{λ_{i}} || ψ_{i} (i = 1, 2). Since n/ψ_{i} (i = 1, 2) must be odd, we must have λ_{1} = λ_{2}. Thus, if λ_{1} ≠ λ_{2}, we have ρ = lcm[τ_{1}, τ_{2}]. If λ_{1} = λ_{2}, then ρ = lcm[ψ_{1}, ψ_{2}] and σ ∤ ρ.

We now have the following result.

Proposition 35. Suppose G = 1, p is a prime such that p ∤ 2P_{1}Q and p | I. If 2 ∤ τ_{1} or 2 ∤ τ_{2}, then p must be monoapparitic in (A_{n}).

Proof. In this case σ = τ_{2} and ρ = lcm[τ_{1}, τ_{2}]. Thus, σ | ρ and the result follows by Proposition 25.

Before proceeding any further we will need some additional results concerning Lehmer sequences. It is easy to establish by induction that if p | r, then for n odd we have

v̄_{n}(r, q) ≡ n(−q)^{\frac{n−1}{2}} (mod p), ū_{n}(r, q) ≡ (−q)^{\frac{n−1}{2}} (mod p).

Thus, if p | r and 2 ∤ n, we have p | v̄_{n}(r, q) ⇔ p | n. Also, if 2 | n and p | r, then ū_{n}(r, q) ≡ n/2(−q)^{n/2} (mod p). Thus, if p | r and 2 | n, then p | ū_{n}(r, q) ⇔ p | n/2. Also, if 2 | n and p | r, then

u_{n}(r, q) ≡ n/2(−q)^{n/2} (mod p).

Thus, if p | r and 2 | n, then p | u_{n}(r, q) ⇔ p | n/2. It follows that (ū_{n}(r, q)) is monoapparitic modulo p when p ∤ 2q.

It is well known ([4, §4]) that p | ū_{p−ϵ}, where ϵ is the value of the Legendre symbol (rd/p). Thus, if p | d, then p | ū_{p} and τ(p) = p. Since p is odd, ψ = ψ(p) does not exist in this case. If p ∤ d, then

p | v̄_{\frac{p−ϵ}{2}} ⇔ (q/p) = −1.

Hence, if (q/p) = −1, then ψ exists and ψ | \frac{p−ϵ}{2}.

A special case of Proposition 35 occurs when (q_{1}/p) = (q_{2}/p) = 1 and ((d_{1}d_{2})/p) = −1. For in this case, τ_{1} | \frac{p−ϵ_{1}}{2} , τ_{2} | \frac{p−ϵ_{2}}{2} . Also, ϵ_{1}ϵ_{2} = ((r_{1}r_{2}d_{1}d_{2})/p) = ((d_{1}d_{2})/p) = −1. It follows that if 2 | τ_{1} and 2 | τ_{2} we get 2 | \frac{p−ϵ_{1}}{2} and 2 | \frac{p−ϵ_{2}}{2} , which means that p ≡ 1 (mod 4) and p ≡ −1 (mod 4), an impossibility.

If G = 1 and S ≠ 1, it is shown in [12] than any odd fourth-order LDS (A_{n}) must have the form given in (54), i.e.,

A_{n} = v_{n}(\sqrt{r_{1}}, q_{1})u_{n}(\sqrt{r_{2}}, q_{2})/\sqrt{r_{1}},  (62)

but it is not always the case that this (A_{n}) will actually be a divisibility sequence. For example, if r_{1} = r_{2} = 7 and q_{2} = 141002, we see that (A_{n}) behaves like a divisibility sequence until we arrive at the 28^{th} term, where we discover that A_{14} is not a divisor of A_{28}. Indeed, as mentioned in [12], it is unlikely that and (A_{n}) exists when G = 1 and S ≠ 1, but this has not yet been proved.

If in (54) we put r = r_{1}, q = q_{1}, μ_{2} = μ_{1}^{s}, ν_{2} = ν_{1}^{s}, then r_{2} = v_{s}(\sqrt{r}, q)^{2} = rv̄_{s}(r, q)^{2} and q_{2} = q^{s}, where s is any fixed odd positive integer. For these values of r_{1}, r_{2}, q_{1}, q_{2}, (62) becomes

A_{n} = v̄_{n}(r, q)ū_{ns}(r, q)/ū_{s}(r, q).  (63)

(This A_{n} is essentially the same function as that discovered by Koshkin [5] when f(x) = (x + 1)(x^{3} − 1) and x = α/β, where α + β = \sqrt{r} and αβ = q.) It can be shown that this (A_{n}) is a fourth-order odd LDS with characteristic polynomial given by (2) with P_{1}, P_{2}, Q defined in (48); also, by using some identities that are satisfied by the Lehmer functions, we have P_{1} = rv̄_{s}(r, q), P_{2} = qv̄_{s−1}(r, q)v̄_{s+1}(r, q), Q = q^{s+1}, Δ = (r − 4q)^{2}ū_{s}(r, q)^{2}, E = (qr(r − 4q)ū_{s−1}(r, q)ū_{s+1}(r, q))^{2}, A_{2} = (r − 2q)v̄_{s}(r, q) and I = 0. Notice that we have S = 1 here.

In the particular case of s = 3, we have P_{1} = r(r − 3q), P_{2} = q(r − 2q)(r^{2} − 4rq + 2q^{2}), Q = q^{4} and A_{2} = (r − 2q)(r − 3q), whereas for (U_{n}) we would have A_{2} = P_{1} = r(r − 3q). If we put r = 5 and q = 1, we get P_{1} = 10, P_{2} = 21, Q = 1,

U_{n} = 0, 1, 10, 76, 540, 3751, 25840, 177451, 1217160, 8344876, 57202750, 392089501, …, (L_{4n} − L_{2n})/4,

and the odd sequence

0, 1, 6, 38, 252, 1705, 11628, 79547, 544824, 3733234, 25585230, 175356611, ….  (64)

These sequences are listed as \underline{A215465} and \underline{A215466}, respectively in the OEIS. The sequence (63) with different values for r and q will also yield the odd LDSs: \underline{A238536} (r = 1, q = −1), \underline{A238537} (r = 4, q = −1) and \underline{A238538} (r = 9, q = 2).

The sequence (64) is an example of a LDS where 2 has the two ranks of appearance 2 and 3. Notice that v̄_{3}(1, 5) = 2. Indeed, if p | v̄_{s}(r, q), then for (A_{n}) given by (63) we have p | P_{1}, p | A_{2}, P_{2} ≡ q^{s}(r − 4q) (mod p) and Q = q^{s+1}. We can now use (58) and (59) to show that

ū_{2n+1}(−P_{2}, Q) ≡ (−1)^{n}q^{ns}v̄_{2n+1}(r, q) (mod p).

Thus, if p | v̄_{s}(r, q), then ψ(p) exists and by Proposition 21 there are two possible ranks of appearance of p in (A_{n}): 2 and ψ. Since ψ | s, we have 2 ∤ ψ and therefore the two ranks are distinct.

Now suppose p ∤ v̄_{s}(r, q) in (63). If p | ū_{s}(r, q), then by (57), we have p | d_{2} and therefore τ_{2} = τ_{2}(p) = p. Since 2 ∤ τ_{2}, p must be monoapparitic in (A_{n}) by Proposition 35. Next, suppose that p ∤ ū_{s}(r, q) and put t = gcd(s, τ_{1}). It is easy to show that τ_{2} = τ_{1}/t in this case. Thus, if t = 1 or 2 ∤ τ_{1}, we have τ_{2} | τ_{1} and consequently p is monoapparitic in (A_{n}). If t > 1 and 2 | τ_{1}, then p has two distinct ranks of apparition in (A_{n}): ω_{1} = σ = τ_{1}/t and ω_{2} = ρ = τ_{1}/2.

If we next select (A_{n}) in (63) with s = 3 and set A_{2} = r(r − 2q), then it turns out that this (A_{n}) is also an odd fourth-order LDS with characteristic polynomial (2) and, as before, P_{1} = r(r − 3q), P_{2} = q(r − 2q)(r^{2} − 4rq + 2q^{2}), Q = q^{4}. Here, it can be shown that

A_{n} = ū_{2n}(r, q)u_{n}(\sqrt{r}, q)^{2} = \begin{cases}v̄_{n}(r, q)ū_{n}^{3}(r, q), & if 2 ∤ n; \\ rv̄_{n}(r, q)ū_{n}^{3}(r, q), & if | n. \end{cases}  (65)

If we put r = 5, q = 1, we get the sequence

0, 1, 15, 128, 945, 6655, 46080, 317057, 2176335, 14925184, 102320625, …, F_{4n} − 2F_{2n},

which appears as \underline{A127595} in the OEIS. This sequence is not monoapparitic modulo 5 as 5 has ranks 2 and 5 in (A_{n}). More generally, if p | r, then by Proposition 21, (A_{n}) in (65) has ranks of appearance ω_{1} = 2 and ω_{2} = p, but if p ∤ r, then p is monoapparitic in (A_{n}) with ω = τ/2 when 2 | τ and ω = τ, otherwise.

If we put r_{1} = t^{2}, q_{1} = q, r_{2} = (t^{2}−2q)^{2}, q_{2} = q^{2} and A_{2} = t^{3}, we find that Δ = t^{2}(t^{2}−4q)^{2} and

A_{n} = u_{n}(t, q)^{3}.  (66)

The corresponding sequence (A_{n}) is clearly odd and a fourth-order LDS. For t = 1, q = −1, we get \underline{A056570} in the OEIS. Also, any prime p is clearly monoapparitic in (A_{n}). We should mention here that versions of (63), (65) and (66) were discovered, using a different approach, by Oosterhout [6].

We have seen, then, that there are infinitely many odd fourth-order LDSs when G = S = 1; are there any others apart from those mentioned here? Possibly, the answer to this question is yes, but no non-trivial examples are known to the authors, none were found during an extensive computer search and none appear in the OEIS.

7 Conclusion

Although we have completely solved the problem of when (A_{n}) can have either one or two ranks of appearance (modulo p), there are still three problems that remain outstanding:

1) Show that no (A_{n}) exists when S ≠ 1, G = 1; 2) Show that no (A_{n}) exists when S = G ≠ 1;

3) Find all possibilities of (A_{n}) when S = G = 1.

8 Acknowledgment

The authors are grateful to Christian Ballot, who carefully read an earlier version of this paper and made a number of helpful and insightful suggestions for improving it. We also wish to thank an anonymous referee, whose careful reading of the original submission of this paper resulted in a substantial improvement in its exposition.

References

[1] M. Abrate, S. Barbero, U. Cerutti, and N. Murru, Linear divisibility sequences and Salem numbers, Pub. Math. Debrecen 91 (2017), 247–259.

[2] S. Barbero, Generalized Vandermonde determinants and characterization of divisibility sequences, J. Number Theory 173 (2017), 371–377.

[3] J.-P. Bézivin, A. Pethö, and A. J. van der Poorten, A full characterization of divisibility sequences, Amer. J. Math. 112 (1990), 985–1001.

[4] D. H. Lehmer, An extended theory of Lucas’ functions, Ann. Math. 31 (1930), 419–448.

[5] Sergiy Koshkin, Non-classical linear divisibility sequences and cyclotomic polynomials, Fibonacci Q. 57 (2019), 68–80.

[6] A. D. Oosterhout, Characterization of divisibility sequences, Master’s Thesis, Utrecht University, (2011).

[7] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Available

   at https://oeis.org.

[8] Morgan Ward, The law of apparition of primes in a Lucasian sequence, Trans. Amer. Math. Soc. 44 (1938), 68–86.

[9] H. C. Williams, Édouard Lucas and Primality Testing, Wiley-Interscience, 1998.

[10] H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Internat. J. Number Theory 7 (2011), 1255–1277.

[11] H. C. Williams and R. K. Guy, Some monoapparitic fourth order divisibility sequences, Integers 12A (2012), A17.

[12] H. C. Williams and R. K. Guy, Odd and even linear divisibility sequences of order 4, Integers 15 (2015), A33.

2010 Mathematics Subject Classification: Primary 11B37; Secondary 11Y11, 11B50. Keywords: linear recurrence, Lucas function.

(Concerned with sequences \underline{A005013}, \underline{A056570}, \underline{A127595}, \underline{A215465}, \underline{A215466}, \underline{A238536}, \underline{A238537}, and \underline{A238538}.)

Received April 7 2021; revised versions received June 5 2021; June 22 2021. Published in Journal of Integer Sequences, July 1 2021.

Return to Journal of Integer Sequences home page.