Some Arithmetic Properties of Certain 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^{1} Department of Mathematics and Statistics University of Calgary 2500 University Drive NW Calgary, AB T2N 1N4 Canada

               williams@math.ucalgary.ca

Abstract

In an earlier paper it was argued that two sequences, denoted by {U_{n}} and {W_{n}}, constitute the sextic analogues of the well-known Lucas sequences {u_{n}} and {v_{n}}. While a number of the properties of {U_{n}} and {W_{n}} were presented, several arithmetic properties of these sequences were only mentioned in passing. In this paper we discuss the derived sequences {D_{n}} and {E_{n}}, where D_{n} = gcd(W_{n} − 6R^{n}, U_{n}) and E_{n} = gcd(W_{n}, U_{n}), in greater detail and show that they possess many number theoretic properties analogous to those of {u_{n}} and {v_{n}}, respectively.

1The second author is supported by NSERC of Canada.

1 Introduction

Let p, q ∈ ℤ be relatively prime and α, β be the zeros of

x^{2} − px + q

with discriminant δ = (α − β)^{2} = p^{2} − 4q. The well-known Lucas sequences {u_{n}} and {v_{n}} are defined by

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

These sequences possess many interesting properties and have found applications in primality testing, integer factorization, solution of quadratic and cubic congruences, and cryptography (see [4]). We note here that both sequences are linear recurrence sequences of order 2 and that u_{n}, v_{n} ∈ ℤ whenever n ≥ 0.

Lucas’ problem of extending or generalizing his sequences has been well studied and we refer the reader to [2, Chapter 1] and [3, Section 1] for further information on this topic. One possible extension of the Lucas sequences, which involves cubic instead of quadratic irrationalities, was investigated in [2] (also see Müller, Roettger and Williams [1]). In this case we let P, Q, R ∈ ℤ be integers such that gcd(P, Q, R) = 1 and let α, β, γ be the zeros of

h(x) = x^{3} − P x^{2} + Qx − R,  (1)

with discriminant

Δ = (α − β)^{2}(β − γ)^{2}(γ − α)^{2} = Q^{2}P^{2} − 4Q^{3} − 4RP^{3} + 18P QR − 27R^{2} ≠ 0.

Roettger’s sequences {c_{n}} and {w_{n}} are defined as

c_{n} = c_{n}(P, Q, R) = (α^{n} − β^{n})(β^{n} − γ^{n})(γ^{n} − α^{n})/((α − β)(β − γ)(γ − α))

and

w_{n} = w_{n}(P, Q, R) = (α^{n} + β^{n})(β^{n} + γ^{n})(γ^{n} + α^{n}) − 2R^{n}.

Note here that if n ≥ 0, we have c_{n}, w_{n} ∈ ℤ and {c_{n}}, {w_{n}} are linear recurrence sequences of order 6.

In [2], it is pointed out that the sequences {c_{n}} and {w_{n}} have many properties analogous to those of {u_{n}} and {v_{n}}, respectively. Recently, these sequences were extended further by Roettger, Williams and Guy [3]. If we put γ_{1} = α/β, γ_{2} = β/γ, γ_{3} = γ/α, λ = R, then we can write

c_{n} = λ^{n−1}(1 − γ_{1}^{n})(1 − γ_{2}^{n})(1 − γ_{3}^{n})/((1 − γ_{1})(1 − γ_{2})(1 − γ_{3})) and
w_{n} = v_{n} − 2R^{n}, where
v_{n} = λ^{n}(1 + γ_{1}^{n})(1 + γ_{2}^{n})(1 + γ_{3}^{n}).

One of the most important properties of the Lucas sequence {u_{n}} when n ≥ 0 is that it is a divisibility sequence. An integer sequence {A_{n}} is said to be a divisibility sequence if A_{n} | A_{m} whenever n | m and A_{n} ≠ 0. For example, Roettger’s sequence {c_{n}} (n ≥ 0) is a divisibility sequence. Suppose we define

U_{n} = \frac{λ^{n−1}(1 − γ_{1}^{n})(1 − γ_{2}^{n})(1 − γ_{3}^{n})}{(1 − γ_{1})(1 − γ_{2})(1 − γ_{3})},  (2)
V_{n} = λ^{n}(1 + γ_{1}^{n})(1 + γ_{2}^{n})(1 + γ_{3}^{n}),  (3)

where λ, γ_{1}, γ_{2}, γ_{3} ∈ ℚ̄; γ_{1}, γ_{2}, γ_{3} ≠ 1; γ_{i} ≠ γ_{j} when i ≠ j and γ_{1}γ_{2}γ_{3} = 1. In [3], it is shown that if U_{n}, V_{n} ∈ ℤ whenever n ≥ 0, {U_{n}} is a linear recurrence sequence and {U_{n}} is also a divisibility sequence, then we must have λ = R ∈ ℤ and ρ_{i} = R(γ_{i} + 1/γ_{i}) (i = 1, 2, 3) must be the zeros of a cubic polynomial

g(x) = x^{3} − S_{1}x^{2} + S_{2}x − S_{3},  (4)

where

S_{3} = RS_{1}^{2} − 2RS_{2} − 4R^{3}  (5)

and S_{1}, S_{2} ∈ ℤ. The six zeros of

G(x) = (x^{2} − ρ_{1}x + R^{2})(x^{2} − ρ_{2}x + R^{2})(x^{2} − ρ_{3}x + R^{2})

= x^{6} − S_{1}x^{5} + (S_{2} + 3R^{2})x^{4} − (S_{3} + 2R^{2}S_{1})x^{3} + R^{2}(S_{2} + 3R^{2})x^{2} − R^{4}S_{1}x + R^{6}

are Rγ_{i}, R/γ_{i} (i = 1, 2, 3). If we define W_{n} = V_{n} − 2R^{n}, then both {U_{n}} and {W_{n}} are linear recurrence sequences with characteristic polynomial G(x). Also, U_{0} = 0, U_{1} = 1, U_{2} = S_{1} + 2R, U_{3} = S_{1}^{2} + RS_{1} − S_{2} − 3R^{2}, W_{0} = 6, W_{1} = S_{1}, W_{2} = S_{1}^{2} − 2S_{2} − 6R^{2}, W_{3} = S_{1}^{3} − 3S_{1}S_{2} + 3RS_{1}^{2} − 6RS_{2} − 3R^{2}S_{1} − 12R^{3}. Furthermore, we have U_{−n} = −U_{n}/R^{2n}, W_{−n} = W_{n}/R^{2n}; hence, U_{n}, W_{n} ∈ ℤ when n ≥ 0. It is also the case that {U_{n}} is a divisibility sequence.

It is shown in [3] that if

S_{1} = P Q − 3R,  S_{2} = P^{3}R + Q^{3} − 5P QR + 3R^{2},  (6)

then U_{n}(S_{1}, S_{2}, R) = c_{n}(P, Q, R), W_{n}(S_{1}, S_{2}, R) = w_{n}(P, Q, R). If, in the expression (2), we define

Δ = λ^{2}(1 − γ_{1})^{2}(1 − γ_{2})^{2}(1 − γ_{3})^{2}
= R^{2}(γ_{1} + γ_{2} + γ_{3} − 1/γ_{1} − 1/γ_{2} − 1/γ_{3})^{2},  (7)

we find that

Δ = S_{1}^{2} − 4S_{2} + 4RS_{1} − 12R^{2},  (8)

but this is the same as Q^{2}P^{2} −4Q^{3} −4RP^{3} +18P QR −27R^{2}, the discriminant of h(x), when S_{1} and S_{2} are given by (6). If d denotes the discriminant of g(x), then, as shown in [3], we have d = ΔΓ, where

Γ = R^{4}(γ_{1} − γ_{2})^{2}(γ_{2} − γ_{3})^{2}(γ_{3} − γ_{1})^{2}  (9)
= S_{2}^{2} + 10RS_{1}S_{2} − 4RS_{1}^{3} − 11R^{2}S_{1}^{2} + 12R^{3}S_{1} + 24R^{2}S_{2} + 36R^{4}.  (10)

The discriminant D of G(x) is given by D = Ed^{2}R^{12}, where

E = R^{2}Δ(S_{1} + 2R)^{2} = (ρ_{1} − 4R^{2})(ρ_{2} − 4R^{2})(ρ_{3} − 4R^{2}).

If S_{1} and S_{2} are given by (6), then

Γ = (RP^{3} − Q^{3})^{2}.  (11)

We remark that the condition analogous to gcd(P, Q, R) = 1 for Roettger’s sequences is gcd(S_{1}, S_{2}, R) = 1 for the more general {W_{n}} and {U_{n}} sequences.

The duplication formulas are

2W_{2n} = W_{n}^{2} + ΔU_{n}^{2} − 4R^{n}W_{n},  U_{2n} = U_{n}(W_{n} + 2R^{n})  (12)

and the triplication formulas are

4W_{3n} = 3ΔU_{n}^{2}(W_{n} + 2R^{n}) + W_{n}^{2}(W_{n} − 6R^{n}) + 24R^{2n},  (13)
4U_{3n} = U_{n}(3W_{n}^{2} + ΔU_{n}^{2}).  (14)

Since {U_{n}} is a divisibility sequence, we must have U_{3n}/U_{n} ∈ ℤ (n ≥ 0) and by (14), this means that 4 | W_{n}^{2} − ΔU_{n}^{2}. Thus, if 2 | U_{n}, then 2 | W_{n} and we have proved Proposition 1.

Proposition 1. If n ≥ 0, then 2 | gcd(W_{n}, U_{n}) if and only if 2 | U_{n}.

The general multiplication formulas for {W_{n}} and {U_{n}} are given as [3, (7.7) and (7.8)].

We observe here that in general for a given S_{1}, S_{2} R ∈ ℤ there do not always exist, P, Q ∈ ℤ such that (6) holds. As a simple example consider S_{1} = −1, S_{2} = −4, and R = 1; it is not possible to find integers P, Q such that P Q = 2 and P^{3} + Q^{3} = 3. Thus, the sequences {W_{n}(S_{1}, S_{2}, R)}, {U_{n}(S_{1}, S_{2}, R)} represent a non-trivial extension of Roettger’s sequences {w_{n}} and {c_{n}}.

In [3] it is mentioned that if we define

D_{n} = gcd(W_{n} − 6R^{n}, U_{n}) and E_{n} = gcd(W_{n}, U_{n}),

then the sequences {D_{n}} and {E_{n}} possess many number theoretic properties in common with {u_{n}} and {v_{n}}, respectively. Indeed, some of these properties were presented in [3] without proof. The purpose of this paper is to supply these proofs or sketches thereof and to develop some new results concerning {D_{n}} and {E_{n}}.

2 Some properties of {D_{n}}

In this section we will produce some results concerning {D_{n}} that are similar to those possessed by {u_{n}}. We begin with two simple propositions that easily follow from Lemma 8.1 of [3] and results immediately following that lemma.

Proposition 2. If gcd(S_{1}, S_{2}, R) = 1, then for n ≥ 0 we have

gcd(D_{n}, R) | 2.

Proposition 3. If gcd(S_{1}, S_{2}, R) = 1, then for any n ≥ 0, we must have 4 ∤ D_{n} whenever 2 | R.

In the sequel we will assume that S_{1}, S_{2}, R have been selected such that gcd(S_{1}, S_{2}, R) = 1. If we define

F_{n} = \begin{cases}ΔU_{n}^{2}, & when 2 ∤ ΔU_{n}; \\ ΔU_{n}^{2}/4, & when 2 | ΔU_{n} \end{cases}

we see that since 4 | W_{n}^{2} − ΔU_{n}^{2}, F_{n} must be an integer. If M is any divisor of F_{n} and (M, R) = 1, then we can use [3, (7.7) and (7.8)] to show that

U_{mn}/U_{n} ≡ R^{n(m−1)}K_{m}(W_{n}/2R^{n}) (mod M),  (15)
W_{mn} ≡ 2R^{mn}L_{m}(W_{n}/2R^{n}) (mod M),  (16)

where the polynomials K_{m}(x) and L_{m}(x) are respectively defined in [2, §4.3 and §5.1]. Also, from results in [2] it is easy to show that L_{m}(3) = 3 and K_{m}(3) = m^{3}. We next establish that like {u_{n}}, {D_{n}} is a divisibility sequence.

Theorem 4. If n, m ≥ 1, then D_{n} | D_{mn}.

Proof. Since {U_{n}} is a divisibility sequence it suffices to show D_{n} | W_{mn} − 6R^{mn}. We let 2^{λ} || D_{n}. If λ = 0 or λ ≥ 1 and 2 ∤ R, then D_{n} | F_{n}. By Proposition 2, we have gcd(D_{n}, R) = 1 and by (16) we get

W_{mn} ≡ 2R^{mn}L_{m}(W_{n}/2R^{n}) ≡ 2R^{mn}L_{m}(3) ≡ 6R^{mn} (mod D_{n}).

If λ = 1, then gcd(D_{n}/2, R) = 1 and D_{n}/2 | F_{n}; hence,

W_{mn} ≡ 6R^{mn} (mod D_{n}/2).

Also, since 2 | U_{n}, we have 2 | U_{mn} and 2 | W_{mn} (Proposition 1). It follows that W_{mn} ≡ 6R^{mn} (mod 2) and since gcd(2, D_{n}/2) = 1 we get

W_{mn} ≡ 6R^{mn} (mod D_{n}).

There remains the case of λ > 1 and 2 | R, but this is impossible by Proposition 3.

Let p be any prime. We are next able to present the law of repetition for p in {D_{n}}. We denote by ν_{p}(x) (x ∈ ℤ) that value of λ such that p^{λ} || x.

Theorem 5. Let p be any prime such that p > 3 and suppose that ν_{p}(D_{n}) ≥ 1.

1. If ν_{p}(U_{n}) > ν_{p}(W_{n} − 6R^{n}), then ν_{p}(D_{pn}) = ν_{p}(D_{n}) + 2 and ν_{p}(W_{pn} − 6R^{pn}) < ν_{p}(U_{pn}).

2. If ν_{p}(U_{n}) = ν_{p}(W_{n} − 6R^{n}) and ν_{p}(U_{n}) > 1, then ν_{p}(D_{pn}) = ν_{p}(D_{n}) + 2 and ν_{p}(W_{pn} − 6R^{pn}) < ν_{p}(U_{pn}).

3. If ν_{p}(U_{n}) < ν_{p}(W_{n} − 6R^{n}), then if ν_{p}(U_{n}) > 1, ν_{p}(D_{pn}) = ν_{p}(D_{n}) + 3.

4. If λ = 1, then ν_{p}(D_{pn}) ≥ 2.

Proof. These results can be established by making use of the techniques of [2, §5.2], together with the polynomial congruence

L_{p}(x) ≡ 3 + p^{2}(x − 3) + (p^{2}(p^{2} − 1)/12)(x − 3)^{2} + (p^{2}(p^{2} − 1)(p^{2} − 4)/360)(x − 3)^{3} (mod (x − 3)^{4}),

which holds for all primes p ≥ 5.

When p = 3, the law of repetition for 3 in {D_{n}} is given below.

Theorem 6. Let ν_{3}(D_{n}) ≥ 1.

1. If ν_{3}(U_{n}) ≥ ν_{3}(W_{n} − 6R^{n}) > 1, then ν_{3}(D_{3n}) = ν_{3}(D_{n}) + 2.

2. If ν_{3}(U_{n}) ≥ ν_{3}(W_{n} − 6R^{n}) = 1, then ν_{3}(D_{3n}) ≥ ν_{3}(D_{n}) + 2.

3. If ν_{3}(U_{n}) < ν_{3}(W_{n} − 6R^{n}), then

ν_{3}(D_{3n}) = ν_{3}(D_{n}) + 3 when ν_{3}(D_{n}) > 1

or

ν_{3}(D_{3n}) ≥ ν_{3}(D_{n}) + 3 when ν_{3}(D_{n}) = 1.

Proof. These results can be easily proved by making use of the the triplication formulas (13) and (14).

In the case of p = 2, there exists a rather complicated law of repetition for p in {D_{n}}. We will not provide the complete law here, but we remark that if ν_{2}(D_{n}) > 1, then the duplication formulas (12) can be used to show that ν_{2}(D_{2n}) ≥ ν_{2}(D_{n}) + 1. The case of ν_{2}(D_{n}) = 1, however, is more problematical. Certainly, if 2 | R, there is no law of repetition for 2 in {D_{n}} by Proposition 3. Thus, we need only consider the case of 2 || D_{n} and 2 ∤ R. In this case, we can use the duplication and triplication formulas to find that if i) 4 | U_{n}, 2 || W_{n} − 6R^{n};

ii) 2 || U_{n}, 2 || W_{n} − 6R^{n}, 2 | Δ;

iii) 2 || U_{n}, 4 | W_{n} − 6R^{n}, 2 ∤ Δ;

then 4 | D_{3n} and 4 ∤ D_{2n}. In all other cases we have 4 | D_{2n}.

We also have the following companion result to the law of repetition for any odd prime in {D_{n}}.

Theorem 7. If p is odd and ν_{p}(D_{n}) ≥ 1, then ν_{p}(D_{mn}) = ν_{p}(D_{n}) whenever p ∤ m.

Proof. Since p ≠ 2, we have p^{2λ} | F_{n} when λ = ν_{p}(D_{n}), gcd(p, R) = 1 and W_{n} ≡ 6R^{n} (mod p^{λ}). It follows from (16) that

W_{mn} ≡ 2R^{mn}L_{m}(W_{n}/2R^{n}) ≡ 2R^{mn}L_{m}(3) ≡ 6R^{mn} (mod p^{λ})

and by (15) that

U_{mn}/U_{n} ≡ R^{n(m−1)}K_{m}(3) ≡ m^{3}R^{n(m−1)} (mod p^{λ}).

Since p ∤ m, it follows that p^{λ} || U_{mn} and p^{λ} | W_{mn} − 6R^{mn}; hence p^{λ} || D_{mn}.

In the case of p = 2, Theorem 7 is not in general true when λ = 1 and 2 ∤ R, as we have seen in the above remarks. Of course, we could eliminate this problem if we could impose additional restrictions on S_{1}, S_{2}, R such that none of i), ii) or iii) could occur. If 2 || D_{n} and 2 ∤ R, it is easy to show that cases i), ii) or iii) can occur if and only if 2 | Q̃_{n}, where Q̃_{n} = (W_{n}^{2} − ΔU_{n}^{2})/4. In a later section we will discuss the parity of Q̃_{n} when 2 | D_{n}. Note that if 4 | D_{n}, then 2 ∤ R and Q̃_{n} ≡ 1 (mod 2). If λ > 1, then we certainly have 2^{λ} | D_{mn} by Theorem 4 and since W_{n}/2R^{n} ≡ 3 (mod 2^{λ−1}), we get

U_{mn}/U_{n} ≡ m^{3}R^{n(m−1)} (mod 2^{λ−1}).

Thus, if m is odd, then 2 ∤ U_{mn}/U_{n} and 2^{λ} || D_{mn}. Hence Theorem 7 is true when p = 2 and ν_{2}(D_{n}) > 1.

We conclude this section with a result that is often useful.

Theorem 8. If m, n ≥ 1, then gcd(U_{mn}/U_{n}, D_{n}) | 2m^{3}.

Proof. It is easy to show this when 2 ∤ D_{n} because D_{n} | F_{n} and gcd(D_{n}, R) = 1. Suppose 2 | D_{n}; then because U_{n}/2 | F_{n}, we have D_{n}/2 | F_{n}. Also, gcd(D_{n}/2, R) = 1 by Propositions 2 and 3. Hence, by (15)

U_{mn}/U_{n} ≡ m^{3}R^{n(m−1)} (mod D_{n}/2).

It follows that

gcd(U_{mn}/U_{n}, D_{n}/2) | m^{3}

and

gcd(U_{mn}/U_{n}, D_{n}) | 2m^{3}.

3 The law of apparition for m in {D_{n}}

In this section we deal with the problem of when m | D_{n}, when m > 1. We note that if p is an odd prime and p | R, then p ∤ D_{n} (n ≥ 0) by Proposition 2. Thus, we may assume that if m is odd, then gcd(m, R) = 1. We define ω = ω(m), if it exists, to be the least positive value of n such that m | D_{n}. We call ω the rank of apparition of m in {D_{n}}.

We begin by examining the case where m is a prime p where p | d and p ∤ 2R.

Theorem 9. Let p by any prime such that p ∤ 2R and p | d. There exists a rank of apparition ω of p in {D_{n}} and if p | D_{n} for some n ≥ 0, then ω | n. Also, ω = p or ω | p ± 1.

Proof. By results in the early part of [3, §9], we know that if p | S_{1}^{2} − 3S_{2}, then p has a simple rank of apparition r_{1} in {U_{n}}. It is not difficult to show that p | D_{n} if and only if r_{1} | n; hence, ω = r_{1}. If p ∤ S_{1}^{2} − 3S_{2}, then p can have two ranks of apparition in {U_{n}} when p | Δ and only one when p ∤ Δ. In either case, it is a simple matter to show that there is a rank of apparition ω of p in {D_{n}}, that ω ≠ p and that if p | D_{n}, then ω | n.

We next consider the case of p = 3 and 3 ∤ d.

Lemma 10. If p = 3 and 3 ∤ dR, then ω = ω(3) always exists in {D_{n}} and if 3 | D_{n}, then ω | n.

Proof. We see from [3, Table 2] that there is single rank of apparition r of 3 in {U_{n}}. From the duplication formulas we see that if 3 | U_{n} and 3 ∤ W_{n}, then 3 | W_{2n} if and only if W_{n} ≡ R^{n} (mod 3) and 3 | W_{4n} if and only if W_{n} ≡ −R^{n} (mod 3). Thus, ω(3) always exists and ω = r, 2r or 4r. Furthermore, if 3 | D_{n}, then ω | n.

There remains the case of odd p where p ∤ 3dR. We first need to establish a simple lemma in this case. Here and in the sequel we will denote by 𝕂_{p} the splitting field of G(x) ∈ 𝔽_{p}[x]. We can denote the zeros of G(x) ∈ 𝔽_{p}[x] by Rγ_{i} and R/γ_{i} (i = 1, 2, 3).

Lemma 11. If p ∤ 2ΔR, then p | D_{n} if and only if γ_{1}^{n} = γ_{2}^{n} = γ_{3}^{n} = 1 in 𝕂_{p}.

Proof. Certainly, if γ_{1}^{n} = γ_{2}^{n} = γ_{3}^{n} = 1 in 𝕂_{p}, then p | W_{n} − 6R^{n} and p | U_{n} by (2) and (3); hence, p | D_{n}. If p | D_{n}, then since p | U_{n} and p ∤ Δ, we may assume without loss of generality that γ_{1}^{n} = 1. By [3, (8.4)], we have γ_{2}^{n} − 1 = 0 and therefore γ_{3}^{n} = 1/(γ_{1}^{n}γ_{2}^{n}) = 1.

Corollary 12. If p ∤ 2ΔR and ω = ω(p) exists for p in {D_{n}}, then p | D_{n} if and only if ω | n.

Proof. Certainly p | D_{n} when ω | n because {D_{n}} is a divisibility sequence. Suppose next that ω ∤ n and p | D_{n}. In this case we have n = qw +r, where 0 < r < ω. Also, by the lemma we must have γ_{1}^{n} = γ_{2}^{n} = γ_{3}^{n} = 1, γ_{1}^{ω} = γ_{2}^{ω} = γ_{3}^{ω} = 1 ∈ 𝕂_{p}. It follows that γ_{1}^{r} = γ_{2}^{r} = γ_{3}^{r} = 1 in 𝕂_{p} and p | D_{r}, which contradicts the definition of ω.

We now deal with the case of p ∤ 6dR. Under this condition, we say that p is an S-prime, Q-prime or I-prime if the splitting field of g(x) ∈ 𝔽_{p}[x] is 𝔽_{p}, 𝔽_{p^{2}} or 𝔽_{p^{3}}, respectively. The following theorem follows easily from Lemma 11 and results in [3, §9].

Theorem 13. If p is a prime, p ∤ 6dR and ϵ = (Δ/p), then

p | D_{p−ϵ} when p is an S-prime,
p | D_{p^{2}−1} when p is an Q-prime,
p | D_{p^{2}+ϵp+1} when p is an I-prime.

We can now assemble the above results in the following theorem.

Theorem 14. If p ∤ 2R, there exists a rank of apparition ω (≤ p^{2} + p + 1) of p in {D_{n}} and if p | D_{n}, then ω | n.

In [2, §4.6], S-, Q-, I-primes are discussed with respect to the polynomial h(x) ∈ 𝔽_{p}[x]. We next show that if S_{1}, S_{2} are given by (6), then the splitting fields of h(x) and g(x) ∈ 𝔽_{p}[x] are the same whenever p ∤ Γ. We let 𝕃_{1} denote the splitting field of h(x) ∈ 𝔽_{p}[x], 𝕃_{2} denote the splitting field of g(x) ∈ 𝔽_{p}[x] and let α, β, γ denote the zeros of h(x) in 𝕃_{1}. Since the zeros of g(x) ∈ 𝔽_{p}[x] are given by

ρ_{1} = γ(α^{2} + β^{2}),  ρ_{2} = α(β^{2} + γ^{2}),  ρ_{3} = β(α^{2} + γ^{2}),

we see that ρ_{1}, ρ_{2}, ρ_{3} ∈ 𝕃_{1}. If 𝕃_{1} = 𝔽_{p}, then clearly 𝕃_{2} = 𝔽_{p} = 𝕃_{1}. If 𝕃_{1} = 𝔽_{p^{2}}, then (Δ/p) = −1 and by (11), we get (d/p) = (ΓΔ/p) = (Δ/p) = −1; hence, 𝕃_{2} = 𝔽_{p^{2}} = 𝕃_{1}. If 𝕃_{1} = 𝔽_{p^{3}}, then (d/p) = 1 and 𝕃_{2} ≠ 𝔽_{p^{2}}. Consider

ρ_{1} = γ(P^{2} − 2Q) − γ^{3} ∈ 𝕃_{1}.

We have

ρ_{1}^{p} = γ^{p}(P^{2} − 2Q) − γ^{3p} = α(P^{2} − 2Q) − α^{3}.

Thus, if ρ_{1} = ρ_{1}^{p}, then since α ≠ γ we must have

α^{2} + αγ + γ^{2} = P^{2} − 2Q

and β^{2} = αγ or β^{3} = R. From (1), we get P β −Q = 0 and P^{3}R−Q^{3} = 0, which is impossible because p ∤ Γ. Thus, ρ_{1} ≠ ρ_{1}^{p}, and therefore 𝕃_{2} = 𝔽_{p^{3}} = 𝕃_{1}.

We have not yet discussed the case of p = 2. The reason for this is easily seen in [3, Table 1]. We first observe that if 2 | R, 2 ∤ S_{1} and 2 | S_{2}, then ω(2) does not exist. Next, if 2 | S_{1} and 2 ∤ S_{2}R, then ω(2) = 2 by definition, but we also have 2 | D_{3} and ω(2) ∤ 3. Thus to truly have a rank of apparition of 2 in the sense of the results given above we should eliminate the possibility that 2 | S_{1} and 2 ∤ S_{2}R. When we do this, then by Proposition 2 we have ω(2) given by Table 1.

If p ∤ 2R, then p has a rank of apparition ω in {D_{n}}; we now deal with the case when m = p^{α} and α > 1. By the law of repetition we know that p^{α} | D_{n} for some n > 0; hence ω(p^{α}) must exist. If we put ω = ω(p), then since p | D_{ω(p^{α})}, we must have ω | ω(p^{α}) by Theorem 14. Put s = ω(p^{α})/ω and let p^{ν} || s, then s = p^{ν}t, where p ∤ t. If p^{λ} || D_{p^{ν}ω} and λ < α, then p^{λ} || D_{p^{ν}ωt} by Theorem 7, which is a contradiction; thus ω(p^{α}) = p^{ν}ω. Notice that ν is the least positive integer such that p^{α} | D_{p^{ν}ω}.

Next, suppose that 2 ∤ m and the prime power decomposition of m is

m = ∏_{i=1}^{k} p_{i}^{α_{i}};

we must have

ω(m) = lcm(ω(p_{i}^{α_{i}}) : i = 1, 2, …, k).  (17)

Thus, if (m, 2R) = 1, then ω(m) always exists and is given by (17).

4 The auxiliary sequences {U_{n}^{∗}} and {W_{n}^{∗}}

In order to prove some results concerning {U_{n}} and {W_{n}}, it is often useful to make use of the auxiliary sequences {U_{n}^{∗}} and {W_{n}^{∗}}. We put γ_{1}^{∗} = γ_{2}/γ_{1}, γ_{2}^{∗} = γ_{3}/γ_{2}, γ_{3}^{∗} = γ_{1}/γ_{3}, R^{∗} = R^{2} and define

V_{n}^{∗} = R^{∗n}(1 + γ_{1}^{∗n})(1 + γ_{2}^{∗n})(1 + γ_{3}^{∗n}),
U_{n}^{∗} = R^{∗n−1}(1 − γ_{1}^{∗n})(1 − γ_{2}^{∗n})(1 − γ_{3}^{∗n})/((1 − γ_{1}^{∗})(1 − γ_{2}^{∗})(1 − γ_{3}^{∗})),
W_{n}^{∗} = V_{n}^{∗} − 2R^{∗n},

where

Δ^{∗} = R^{∗2}(1 − γ_{1}^{∗})^{2}(1 − γ_{2}^{∗})^{2}(1 − γ_{3}^{∗})^{2} = Γ ≠ 0.  (18)

Notice also that

Γ^{∗} = R^{∗4}(γ_{1}^{∗} − γ_{2}^{∗})^{2}(γ_{2}^{∗} − γ_{3}^{∗})^{2}(γ_{3}^{∗} − γ_{1}^{∗})^{2}
= ΔR^{2}U_{3}^{2}.

If we put γ_{1}^{∗∗} = γ_{2}^{∗}/γ_{1}^{∗} = 1/γ_{2}^{3}, then γ_{1}^{∗∗} = 1/γ_{2}^{3}. We also have γ_{2}^{∗∗} = γ_{3}^{∗}/γ_{2}^{∗} = 1/γ_{3}^{3}, γ_{3}^{∗∗} = γ_{1}^{∗}/γ_{3}^{∗} = 1/γ_{1}^{3}; hence,

W_{n}^{∗∗} = R^{n}W_{3n},  U_{n}^{∗∗} = R^{n−1}U_{3n}/U_{3}.  (19)

If we put ρ_{i}^{∗} = R^{∗}(γ_{i}^{∗} + 1/γ_{i}^{∗}) (i = 1, 2, 3), we get

S_{1}^{∗} = ρ_{1}^{∗} + ρ_{2}^{∗} + ρ_{3}^{∗} = S_{2} − RS_{1}  (20)

and

S_{2}^{∗} = ρ_{1}^{∗}ρ_{2}^{∗} + ρ_{2}^{∗}ρ_{3}^{∗} + ρ_{3}^{∗}ρ_{1}^{∗} = RW_{3} + R^{2}S_{1}^{∗}
= RS_{1}^{3} − 3RS_{1}S_{2} + 3R^{2}S_{1} − 5R^{2}S_{2} − 4R^{3}S_{1} − 12R^{4}.  (21)

Also,

S_{3}^{∗} = ρ_{1}^{∗}ρ_{2}^{∗}ρ_{2}^{∗}
= R^{∗}S_{1}^{∗2} − 2R^{∗}S_{2}^{∗} − 4R^{∗3}.

It follows, then, from the results mentioned in §1, that if we compute the initial values of U_{n}^{∗} and W_{n}^{∗}(= V_{n}^{∗} − 2R^{∗n}) by replacing R, S_{1}, S_{2} by R^{∗}, S_{1}^{∗}, S_{2}^{∗}, respectively, then we have both {U_{n}^{∗}} and {W_{n}^{∗}} to be linear recurrence sequences of order 6 with characteristic polynomial G^{∗}(x) and {U_{n}^{∗}} is a divisibility sequence. It is easy to show as well that W_{−n}^{∗} = W_{n}^{∗}/R^{∗2n} and U_{−n}^{∗} = −U_{n}^{∗}/R^{∗2n}. We observe further that gcd(S_{1}^{∗}, S_{2}^{∗}, S_{3}^{∗}) = 1 if and only if gcd(S_{1}, S_{2}, S_{3}) = 1. Thus, the sequences {U_{n}^{∗}} and {W_{n}^{∗}} have the same properties as {U_{n}} and {W_{n}} with R, S_{1}, S_{2}, replaced by R^{∗}, S_{1}^{∗}, S_{2}^{∗}, respectively.

We have shown how to relate the {U_{n}^{∗∗}} and {W_{n}^{∗∗}} sequences to {U_{n}} and {W_{n}} in (19); we can also relate the {U_{n}^{∗}} and {W_{n}^{∗}} sequences to {U_{n}} and {W_{n}}. We define ρ_{i}^{(n)} = R^{n}(γ_{i}^{n} + 1/γ_{i}^{n}) (i = 1, 2, 3) and find that

S_{1}^{(n)} = ρ_{1}^{(n)} + ρ_{2}^{(n)} + ρ_{3}^{(n)} = W_{n}  (22)

and

S_{2}^{(n)} = ρ_{1}^{(n)}ρ_{2}^{(n)} + ρ_{2}^{(n)}ρ_{3}^{(n)} + ρ_{1}^{(n)}ρ_{3}^{(n)} = W_{n}^{∗} + R^{n}W_{n}.  (23)

Since

ΔU_{n}^{2} = R^{2n}(1 − γ_{1}^{n})^{2}(1 − γ_{2}^{n})^{2}(1 − γ_{3}^{n})^{2}
= S_{1}^{(n)2} − 4S_{2}^{(n)} + 4R^{n}S_{1}^{(n)} − 12R^{2n},

we get

ΔU_{n}^{2} = W_{n}^{2} − 4W_{n}^{∗} − 12R^{2n}  (24)

using (22) and (23). This formula, which generalizes (8), is similar to the well-known Lucas function identity

v_{n}^{2} − δu_{n}^{2} = 4q^{n}.

Note also that we get

Q̃_{n} = W_{n}^{∗} + 3R^{n}  (25)

from (24) and

4W_{n}^{∗} = W_{n}^{2} − ΔU_{n}^{2} − 12R^{2n},

the relation connecting W_{n}^{∗} to W_{n} and U_{n}. To relate U_{n}^{∗} to W_{n} and U_{n} is somewhat more complicated. From (24), we have

Δ^{∗}U_{n}^{∗2} = W_{n}^{∗2} − 4W_{n}^{∗∗} − 12R^{∗2n}.

Hence, from (18), (19), and (24), we get

ΓU_{n}^{∗2} = ((W_{n}^{2} − ΔU_{n}^{2})/4 − 3R^{2n})^{2} − 4R^{n}W_{3n} − 12R^{4n}.

From (13), we find that

16ΓU_{n}^{∗2} = W_{n}^{4} − 16R^{n}W_{n}^{3} − 48R^{n}ΔW_{n}U_{n}^{2} + 72R^{2n}W_{n}^{2} − 72R^{2n}ΔU_{n}^{2} − 2ΔW_{n}^{2}U_{n}^{2} + Δ^{2}U_{n}^{4} − 432R^{4n}, (26)

a formula that generalizes (10).

As promised in §2 we will now investigate the parity of Q̃_{n} when 2 ∤ R and 2 | D_{n}. If 2 ∤ S_{1} and 2 | S_{2}, then by (20) and (21), we have 2 ∤ S_{1}^{∗} and 2 | S_{2}^{∗}. It follows that 2 | U_{n}^{∗} if and only if 7 | n and 2 | W_{n}^{∗} when 2 | D_{n}. In this case we find from (25) that 2 ∤ Q̃_{n} whenever 2 | D_{n}. If 2 | S_{1} and 2 | S_{2}, then 2 | S_{1}^{∗} and 2 | S_{2}^{∗}; hence, 2 | U_{n}^{∗} if and only if 2 | n and we get 2 | W_{n}^{∗}, Q̃_{n} ≡ 1 (mod 2) whenever 2 | D_{n}. If 2 ∤ S_{1} and 2 ∤ S_{2}, then Δ^{∗} = Γ ≡ (S_{2} + RS_{1})^{2} ≡ 0 (mod 4) from (10). Since 4 | W_{n}^{∗2} − Δ^{∗}U_{n}^{∗2}, we get 2 | W_{n}^{∗} and Q̃_{n} ≡ 1 (mod 2).

The only remaining case is 2 | S_{1} and 2 ∤ S_{2}. In this case 4 | Δ and case (iii) can never occur. We get U_{2} ≡ S_{1} + 2 (mod 4) and W_{2} − 6R^{2} ≡ 2 (mod 4); thus, we see that cases (i) and (ii) can always occur, depending on the parity of S_{1}/2. In either of these cases, we get 4 | D_{6}. It follows that if we eliminate the case of 2 | S_{1} and 2 ∤ S_{2}R, then Thereom 7, will be true for all primes p. Also, we have already seen in §3 that if we eliminate this case, then we have a rank of apparition ω of 2 in {D_{n}} and 2 | D_{n} if and only if ω | n; indeed, if gcd(m, R) = 1, there always exists a rank of apparition ω of m in {D_{n}} given by (17) such that m | D_{n} if and only if ω | n. We remark here that if S_{1} and S_{2} are given by (6), then if 2 ∤ R and 2 | S_{1}, we must have 2 | S_{2}. Thus, for the sequences {c_{n}} and {w_{n}} we cannot have the case of 2 | S_{1} and 2 ∤ S_{2}R.

If p is an I-prime and p ≡ ϵ = (Δ/p) (mod 3), then 3 | p^{2} + ϵp + 1. Since we know in this case that p | D_{p^{2}+ϵp+1}, it is of some interest to determine a criterion for deciding whether or not p | D_{(p^{2}+ϵp+1)/3}. Roettger showed for the case of the {c_{n}} and {w_{n}} sequences that p | D_{(p^{2}+p+1)/3} (ϵ = 1 in this case if p is an I-prime) if and only if R^{(p−1)/3} ≡ 1 (mod p) in [2, Theorem 5.14]. In what follows we will extend this result to the {U_{n}} and {W_{n}} sequences. We begin with three preliminary lemmas.

Lemma 15. If 3W_{1}^{2} ≡ −Δ (mod p), then p cannot be an I-prime.

Proof. We have W_{1} = S_{1} and by (8) we find that

S_{2} ≡ RS_{1}^{2} − 2RS_{1} − 4R^{3} (mod p)

and by (5)

S_{3} ≡ −RS_{1}^{2} − 2R^{2}S_{1} + 2R^{3} (mod p).

Hence

g(x) ≡ (x + R)(x^{2} − (S_{1} + R)x + S_{1}^{2} + 2RS_{1} − 2R^{2}) (mod p).

Since g(x) is reducible modulo p, p cannot be an I-prime. Lemma 16. Let p be an I-prime and let 𝕂_{p} be the splitting field of G(x) ∈ 𝔽[x]. If ζ is a primitive cube root of unity in 𝕂_{p}, then in 𝕂_{p} we can have

ζ^{k}(γ_{1} + γ_{2} + γ_{3}) + ζ^{−k}(γ_{1}^{−1} + γ_{2}^{−1} + γ_{3}^{−1}) = γ_{1} + γ_{2} + γ_{3} + γ_{1}^{−1} + γ_{2}^{−1} + γ_{3}^{−1} (27)

if and only if 3 | k. Proof. If 3 | k it is trivial that (27) must hold. If 3 ∤ k, we first observe that ζ^{k} + ζ^{−k} = −1 and we have

ζ^{k} + 1/2 = (ζ^{k} − ζ^{−k})/2,  ζ^{−k} + 1/2 = (ζ^{−k} − ζ^{k})/2.

Thus (27) can hold only if

\frac{ζ^{k} − ζ^{−k}}{2} (γ_{1} + γ_{2} + γ_{3} − γ_{1}^{−1} − γ_{2}^{−1} − γ_{3}^{−1}) = \frac{3}{2}(γ_{1} + γ_{2} + γ_{3} + γ_{1}^{−1} + γ_{2}^{−1} + γ_{3}^{−1}).

On multiplying both sides by 2R and squaring we find that

3W_{1}^{2} ≡ −Δ (mod p),

which by the previous lemma is impossible. Lemma 17. If p is an I-prime and p | U_{n}, then p | D_{n}. Proof. Since p | U_{n}, we must have γ_{i}^{n} = 1 in 𝕂_{p} for some i ∈ {1, 2, 3} by (2). We may assume that γ_{1}^{n} = 1. From the proof of [3, Theorem 9.8], we have 1 = γ_{1}^{pn} = γ_{2}^{±n}; hence, γ_{2}^{n} = 1 and γ_{3}^{n} = 1/(γ_{1}^{n}γ_{2}^{n}) = 1. The result now follows by Lemma 11.

We are now able to derive our criterion for when p | D_{(p^{2}+ϵp+1)/3}. Theorem 18. If p is an I-prime and p ≡ ϵ (mod 3), then p | D_{(p^{2}+ϵp+1)/3} if and only if

W_{(p−ϵ)/3}^{∗} ≡ R^{2(p−ϵ)/3−1}W_{1} (mod p).

Proof. We first note by Lemma 17 and 11 that p | U_{(p^{2}+ϵp+1)/3} if and only if γ_{i}^{(p^{2}+ϵp+1)/3} = 1 in 𝕂_{p} for all i ∈ {1, 2, 3}. Since γ_{1}^{p^{2}+ϵp+1} = 1 in 𝕂_{p}, we must have

γ1^{\frac{p^{2}+ϵp+1}{3}} = ζ^{k},

where ζ is a primitive cube root of unity in 𝕂_{p}. It follows that p | D_{(p^{2}+ϵp+1)/3} if and only if 3 | k. Now

(p^{2} + ϵp + 1)/3 = (p − ϵ)(p + 2ϵ)/3 + 1.

Hence,

ζ^{k} = γ_{1}^{(p^{2}+ϵp+1)/3} = (γ_{1}^{p+2ϵ})^{(p−ϵ)/3}γ_{1}.

Since γ_{1}^{p} = γ_{2}^{ϵ} (see the proof of [3, Theorem 9.8]), we get

ζ^{k} = (γ_{2}γ_{1}^{2})^{ϵ(p−ϵ)/3}γ_{1} = γ_{3}^{∗ϵ(p−ϵ)/3}γ_{1}

and

γ_{3}^{∗(p−ϵ)/3} = (ζ^{k}/γ_{1})^{ϵ}.

Since γ_{3}^{∗p} = γ_{1}^{p}/γ_{3}^{p} = γ_{2}^{ϵ}/γ_{1}^{ϵ} = γ_{1}^{∗ϵ}, we get

γ_{1}^{∗ϵ(p−ϵ)/3} = (ζ^{kp}/γ_{1}^{p})^{ϵ} = ζ^{k}/γ_{2}

and

γ_{1}^{∗(p−ϵ)/3} = (ζ^{k}/γ_{2})^{ϵ}.

Similarly γ_{2}^{∗(p−ϵ)/3} = (ζ^{k}/γ_{3})^{ϵ}. It follows that

W_{(p−ϵ)/3}^{∗} = R^{∗(p−ϵ)/3}[ζ^{−kϵ}(γ_{1}^{ϵ} + γ_{2}^{ϵ} + γ_{3}^{ϵ}) + ζ^{kϵ}(γ_{1}^{−ϵ} + γ_{2}^{−ϵ} + γ_{3}^{−ϵ})].

By Lemma 16, we see that 3 | k if an only if

W_{(p−ϵ)/3}^{∗} ≡ R^{2(p−ϵ)/3−1}W_{1} (mod p).

This criterion can easily be converted to one that involves only the {U_{n}} and {W_{n}} sequences by using (24). At first glance, the criterion of Theorem 18 does not resemble the more elegant rule for p | D_{(p^{2}+ϵp+1)/3} when dealing with Roettger’s sequences. In this case we have γ_{1} = α/β, γ_{2} = β/γ, γ_{3} = γ/α and R = αβγ. We can deduce Roettger’s rule in the following corollary of Theorem 18.

Corollary 19. Suppose D_{n} = gcd(w_{n} − 6R^{n}, c_{n}) and p is an I-prime with respect to h(x) ∈ 𝔽_{p}[x], then if p ≡ 1 (mod 3), we have

p | D_{(p^{2}+ϵp+1)/3} ⇔ R^{(p−1)/3} ≡ 1 (mod p).

Proof. Suppose first that p ∤ Γ. In this case p is an I-prime with respect to g(x) ∈ 𝔽_{p}[x] and 1 = (d/p) = (ΓΔ/p) = (Δ/p) = ϵ. By Theorem 18 we have p | D_{(p^{2}+ϵp+1)/3} if and only if W_{(p−ϵ)/3}^{∗} ≡ R^{2(p−ϵ)/3−1}W_{1} (mod p). But in 𝕂_{p}, we have γ_{1}^{∗} = γ_{2}/γ_{1} = β^{2}/(αγ) = β^{3}/R; hence,

γ_{1}^{∗ \frac{p−1}{3}} = β^{p−1}/R^{(p−1)/3} = (α/β)/R^{(p−1)/3} = γ_{2}^{−1}/R^{(p−1)/3}.

Similarly, γ_{2}^{∗ \frac{p−1}{3}} = γ_{3}^{−1}/R^{(p−1)/3}, γ_{3}^{∗ \frac{p−1}{3}} = γ_{1}^{−1}/R^{(p−1)/3}. It follows that

W ∗_{\frac{p−1}{3}} = R^{∗(p−1)/3}(R^{(p−1)/3}(γ_{1} + γ_{2} + γ_{3}) + R^{−(p−1)/3}(γ_{1}^{−1} + γ_{2}^{−1} + γ_{3}^{−1}))

and by Lemma 16 W ∗_{\frac{p−1}{3}} ≡ R^{2(p−1)/3−1}W_{1} (mod p), if and only if R^{(p−1)/3} = 1 in 𝕂_{p}.

Suppose next that p | Γ. In this case, p cannot be an I-prime with respect to g(x). If p ∤ P, then by (11) we have R ≡ (Q/P)^{3} (mod p) and h(Q/P) ≡ 0 (mod p). In this case p is not an I-prime with respect to h(x), a contradiction. If p | P, then p | Q and α^{3} = β^{3} = γ^{3} = R in 𝕃_{1}. We have α^{p−1} = β^{p−1} = γ^{p−1} = R^{(p−1)/3} and if R^{(p−1)/3} ≡ 1 (mod p), we get α^{p} = α, and p is not an I-prime with respect to h(x) ∈ 𝔽_{p}[x], a contradiction. Now p | D_{3} and since 3 ∤ (p^{2} + ϵp + 1)/3, we have p ∤ D_{(p^{2}+ϵp+1)/3}. Thus, if p is an I-prime with respect to h(x) ∈ 𝔽_{p}[x], then R^{(p−1)/3} ≢ 1 (mod p) and p ∤ D_{(p^{2}+ϵp+1)/3}.

We conclude this section with the following result concerning

D_{n}^{∗} = gcd(W_{n}^{∗} − 6R^{∗n}, U_{n}).

Theorem 20. If p is an I-prime and p ≡ ϵ (mod 3), then p | D_{(p^{2}+ϵp+1)/3}^{∗}.

Proof. We observe as above that γ_{1}^{∗} = γ_{2}/γ_{1} and

(p^{2} + ϵp + 1)/3 = (p − ϵ)(p + 2ϵ)/3 + 1.

Hence

γ_{1}^{∗(p^{2}+ϵp+1)/3} = (γ_{2}/γ_{1})((γ_{2}/γ_{1})^{p+2ϵ})^{(p−ϵ)/3}

in 𝕂_{p}. Now γ_{2}^{p} = γ_{3}^{ϵ}, γ_{1}^{p} = γ_{2}^{ϵ}; hence,

(γ_{2}/γ_{1})^{p+2ϵ} = (γ_{2}γ_{3}/γ_{1}^{2})^{ϵ} = γ_{1}^{−3ϵ}.

It follows that

((γ_{2}/γ_{1})^{p+2ϵ})^{(p−ϵ)/3} = γ_{1}^{−ϵ(p−ϵ} = γ_{1}/γ_{2}

and

γ_{1}^{∗(p^{2}+ϵp+1)/3} = 1.

Hence, p | D_{(p^{2}+ϵp+1)/3}^{∗}.

5 Some properties of {E_{n}}

We will devote the major portion of this section to the proof that if p (> 3) is a prime and p | E_{n}, then p ≡ (Γ/p) (mod 3). This generalizes [2, Theorem 6.2]. We observe that by Proposition 2 we have gcd(E_{n}, R) = 2. We now need some preliminary results.

Lemma 21. Let p be any prime such that p > 3. If p | E_{n}, then in 𝕂_{p} we must have

γ_{i}^{n} = 1,  γ_{j}^{2n} + γ_{j}^{n} + 1 = 0,

where i ∈ {1, 2, 3} and all j ∈ {1, 2, 3} such that j ≠ i.

Proof. If p ∤ Δ and p | U_{n}, we may assume with no loss of generality that γ_{1}^{n} = 1 in 𝕂_{p}. If p | Δ we may assume with no loss of generality that γ_{1} = 1 (and γ_{1}^{n} = 1) in 𝕂_{p}. Now

W_{n} = V_{n} − 2R^{n} = R^{n}(1 + γ_{1}^{n})(1 + γ_{2}^{n})(1 + γ_{3}^{n}) − 2R^{n}
= 2R^{n}(γ_{2}^{n}γ_{3}^{n} + γ_{2}^{n} + γ_{3}^{n})
= 2R^{n}(1 + γ_{2}^{n} + 1/γ_{2}^{n})
= 2R^{n}(1 + 1/γ_{3}^{n} + γ_{3}^{n}),

the latter results following from γ_{1}^{n} = 1 and γ_{1}^{n}γ_{2}^{n}γ_{3}^{n} = 1. Since W_{n} = 0 in 𝕂_{p}, we have γ_{2}^{2n} + γ_{2}^{n} + 1 = γ_{3}^{2n} + γ_{3}^{n} + 1 = 0.

Lemma 22. If p (> 3) is a prime, then p ∤ (E_{n}, Γ).

Proof. If p | Γ, then γ_{1} = γ_{2}, γ_{2} = γ_{3} or γ_{3} = γ_{1} in 𝕂_{p} by (10). If p | E_{n}, then we may assume that γ_{1}^{n} = 1 and γ_{2}^{2n} + γ_{2}^{n} + 1 = 0 in 𝕂_{p} by Lemma 21. If γ_{1} = γ_{2}, then γ_{2}^{n} = 1, which is impossible because p > 3. The same is true if γ_{2} = γ_{3} or γ_{3} = γ_{1}.

Lemma 23. If p (> 3) is a prime, p | Δ and p | E_{n}, then

p ≡ (Γ/p) (mod 3).

Proof. Since p | Δ, we may assume with no loss of generality that γ_{1} = 1 and therefore γ_{2}γ_{3} = 1 in 𝕂_{p} = 𝔽_{p^{2}}. Also, by Lemma 21 we may assume that if p | E_{n}, then

γ_{2}^{2n} + γ_{2}^{n} + 1 = 0

in 𝕂_{p}. Hence, γ_{2}^{3n} = 1 and γ_{2}^{n} ≠ 1 in 𝕂_{p}. By Lemma 22, p ∤ Γ and

Γ^{\frac{p−1}{2}} = (γ_{1} − γ_{2})^{p−1}(γ_{2} − γ_{3})^{p−1}(γ_{3} − γ_{1})^{p−1}
= \frac{(1 − γ_{2}^{p})(γ_{2}^{p} − γ_{3}^{p})(γ_{3}^{p} − 1)}{(1 − γ_{2})(γ_{2} − γ_{3})(γ_{3} − 1)}.  (28)

If γ_{2} ∈ 𝔽_{p}, then Γ^{\frac{p−1}{2}} = 1. Also, from γ_{2}^{pn} = γ_{2}^{n}, we get γ_{2}^{(p−1)n} = 1, which, since γ_{2}^{n} ≠ 1 means that 3 | p − 1 and p ≡ (Γ/p) (mod 3). If γ_{2} ∈ 𝔽_{p^{2}}\𝔽_{p}, then γ_{2}^{p} = γ_{3} and γ_{2}^{(p−1)n} = −1 by (28). Since γ_{2}^{pn} = γ_{3}^{n} = 1/γ_{2}^{n} and γ_{2}^{(p+1)n} = 1, we see that 3 | p + 1 and p ≡ (Γ/p) (mod 3).

We now show that if p is an I-prime, then p ∤ E_{n}.

Theorem 24. If p is an I-prime, then p ∤ E_{n}.

Proof. As noted above we know that if p is an I-prime, then γ_{1}^{p} = γ_{2}^{ϵ}, γ_{2}^{p} = γ_{3}^{ϵ}, γ_{3}^{p} = γ_{1}^{ϵ} in 𝕂_{p}. If p | E_{n}, then by Lemma 21, we have γ_{1}^{n} = 1 and γ_{2}^{2n} +γ_{2}^{n} +1 = 0. Now γ_{2}^{p^{2}} = γ_{3}^{ϵp} = γ_{1}^{ϵ^{2}} = γ_{1} and γ_{2}^{p^{2}n} = γ_{1}^{n}. Hence,

0 = (γ_{2}^{2n} + γ_{2}^{n} + 1)^{p^{2}} = 3,

which is a contradiction.

We next deal with the case where p | S_{1} + 2R.

Lemma 25. If p (> 3) is a prime, p ∤ d, p | S_{1} + 2R and p | E_{n}, then

p ≡ (Γ/p) (mod 3).

Proof. Since p | S_{1} + 2R and S_{1} + 2R = R(γ_{1} + 1)(γ_{2} + 1)(γ_{3} + 1), we may assume in 𝕂_{p} that γ_{1} = −1 and γ_{2}γ_{3} = −1. We get

(γ_{1} + γ_{2})(γ_{2} + γ_{3})(γ_{3} + γ_{1}) = −(γ_{2}^{2} + 1/γ_{2}^{2} − 2).

Since S_{1} ≡ −2R (mod p), we get S_{3} ≡ −2RS_{2} (mod p) from (5) and

g(x) = (x + 2R)(x^{2} + S_{2}) ∈ 𝔽_{p}[x].

Since ρ_{1} = R(γ_{1} + 1/γ_{1}) = −2R, we get ρ_{2}^{2} = ρ_{3}^{2} = −S_{2} and γ_{2}^{2} + 1/γ_{2}^{2} = ρ_{2}^{2}/R^{2} − 2 = −S_{2}/R^{2} − 2 ∈ 𝔽_{p}. It follows that (γ_{1} + γ_{2})(γ_{2} + γ_{3})(γ_{3} + γ_{1}) ∈ 𝔽_{p} and

((γ_{1}^{2} − γ_{2}^{2})(γ_{2}^{2} − γ_{3}^{2})(γ_{3}^{2} − γ_{1}^{2}))^{p−1} = ((γ_{1} − γ_{2})^{2}(γ_{2} − γ_{3})^{2}(γ_{3} − γ_{1})^{2})^{\frac{p−1}{2}}
= (Γ/p).  (29)

As γ_{2}^{2} + 1/γ_{2}^{2} ∈ 𝔽_{p}, we must have γ_{2}^{2}, 1/γ_{2}^{2} ∈ 𝔽_{p^{2}} and γ_{2}^{2p} = γ_{2}^{2} or γ_{2}^{2p} = γ_{3}^{2}. Since p ∤ d, we see from (29), that (Γ/p) = 1, when γ_{2}^{2p} = γ_{2}^{2} and (Γ/p) = −1, when γ_{2}^{2p} = γ_{3}^{2}.

If p | E_{n}, then by Lemma 21, we have γ_{i}^{n} = 1 for some i ∈ {1, 2, 3} and γ_{j}^{2n} + γ_{j}^{n} + 1 = 0 (i ≠ j). Since γ_{1} = −1, we see that i = 1 and 2 | n. If (Γ/p) = 1, then γ_{2}^{np} = γ_{2}^{n} and γ_{2}^{n(p−1)} = 1. Since γ_{2}^{3n} = 1 and γ_{2}^{n} ≠ 1, we see that 3 | p − 1 and p ≡ (Γ/p) (mod 3). If (Γ/p) = −1, then γ_{2}^{np} = γ_{3}^{n} = 1/γ_{2}^{n} and γ_{2}^{n(p+1)} = 1; hence 3 | p + 1 and p ≡ (Γ/p) (mod 3).

We are now ready to prove our main result.

Theorem 26. If p (> 3) is a prime divisor of E_{n}, then p ≡ (Γ/p) (mod 3).

Proof. We have already proved this result when p | d and when p ∤ d and p | S_{1} + 2R. We may assume, then, that p ∤ d and p ∤ S_{1} + 2R. Since p | E_{n}, p can only be an S-prime or a Q-prime by Theorem 24. If p is an S-prime, then 1 = (d/p) = (Δ/p)(Γ/p) and (Γ/p) = ϵ; if p is an Q-prime, then −1 = (d/p) = (Δ/p)(Γ/p) and (Γ/p) = −ϵ. Suppose p is an S-prime. By results in the proof of [3, Theorem 9.4], we have γ_{i}^{p} = γ_{i}^{ϵ} (i = 1, 2, 3) in 𝕂_{p}. By Lemma 21, we get γ_{2}^{3n} = 1, γ_{2}^{n} ≠ 1; also, γ_{2}^{np} = γ_{2}^{nϵ} means that γ_{2}^{(p−ϵ)n} = 1 and 3 | p − ϵ. Similarly, if p is a Q-prime, then by the results in the proof of [3, Theorem 9.6], we have

γ_{2}^{p} = γ_{3}^{ϵ},  γ_{3}^{p} = γ_{2}^{ϵ},  γ_{3}^{p} = γ_{1}^{ϵ}

in 𝕂_{p}. In this case we get γ_{2}^{pn} = γ_{3}^{ϵn} = (1/γ_{2})^{ϵn} and γ_{2}^{n(p+ϵ)} = 1, γ_{2}^{3n} = 1 and γ_{2}^{n} ≠ 1. Hence 3 | p + ϵ and in either case p ≡ (Γ/p) (mod 3).

In order to extend Theorem 26, we need to prove the following result.

Theorem 27. For any n > 0, we have E_{n} | D_{3n}.

Proof. We can rewrite (13) as

W_{3n} − 6R^{3n} = (W_{n} − 6R^{n})Q̃_{n} + ΔW_{n}U_{n}^{2},  (30)

where Q̃_{n} = (W_{n}^{2} − ΔU_{n})/4. Suppose p is any odd prime and p^{λ} || E_{n}, where λ ≥ 1. Since p^{λ} | U_{n}, we must have p^{λ} | U_{3n}. Also, p^{2λ} | Q̃_{n} and p^{λ} | W_{3n} − 6R^{3n} by (30). Next, suppose that 2^{λ} || E_{n} and λ ≥ 1. We have 2 | W_{n} − 6R^{n} and 2^{2λ−2} | Q̃_{n}, 2^{λ} | U_{n}. By (30) we see that 2^{2λ−1} | W_{3n} − 6R^{3n} and since λ ≥ 1, we have 2λ − 1 ≥ λ and 2^{λ} | D_{3n}. Hence, E_{n} | D_{3n}.

We next prove a result which is analogous to the theorem that states that if p is an odd prime and p | v_{n}, then p ≡ ±1 (mod 2^{ν+1}), where 2^{ν} || n. (See [2, Theorem 2.20]).

Theorem 28. If p (> 3) is a prime and p | E_{n}, then p ≡ (Γ/p) (mod 3^{ν+1}), where 3^{ν} || n.

Proof. Since p | E_{n} and p > 3, we have p ∤ D_{n}, as p ∤ 6R. But, by Theorem 27, we know that p | D_{3n}. Thus, if ω is the rank of apparition of p in {D_{n}}, we have ω | 3n and ω ∤ n. It follows that 3^{ν+1} | ω. Also, since p is not an I-prime and p ∤ 6R, we must have ω = p or ω | p^{2} − 1 by results in §3. Since 3 | ω we cannot have ω = p and therefore ω | p^{2} − 1 and 3^{ν+1} | p^{2} − 1. Since p ∤ Γ, we have p^{2} − 1 = (p − (Γ/p))(p + (Γ/p)) and 3 | p − (Γ/p). Hence 3^{ν+1} | p − (Γ/p).

6 Primality tests

In Williams [4], it is shown how Lucas used the properties of {u_{n}} and {v_{n}} to develop primality tests for certain families of integers. In this section we will indicate how the properties of {U_{n}} and {W_{n}} can be used to produce some primality tests. We begin with a simple result concerning integers of the form A3^{n} + η, where η^{2} = 1.

Theorem 29. Let N = A3^{n} + η, where 2 | A, n ≥ 2, 3 ∤ A, η ∈ {1, −1} and A < 3^{n}. If

N | U_{N−η}/U_{(N−η)/3},

then N is a prime.

Proof. Let p be any prime divisor of N and put m = (N − η)/3. We note that p ≠ 2, 3 and by (14)

4U_{3m}/U_{m} = 3W_{m}^{2} + ΔU_{m}^{2}.

Since p | U_{3m}, there must exist some rank of apparition r of p in {U_{n}} such that r | 3m. If p | U_{m} and p | W_{m}, then p | E_{m} and p ≡ (Γ/p) (mod 3^{n}) by Theorem 28. If p ∤ U_{m}, then r ∤ m and r | 3m means that 3^{n} | r. Suppose p ∤ dR. If p is an S-prime or a Q-prime, then by [3, Corollary 9.5 and Theorem 9.7] we must have r | p−ϵ, where ϵ = (Δ/p); hence p ≡ (Δ/p) (mod 3^{n}). If p is an I-prime, then r | p^{2} + ϵp + 1 by Theorem 9.9 of [3]. Since 9 | r, this is impossible. If p | dR, then r = 3, p or divides p ± 1. Since 9 | r, r ≠ 3 and since p ∤ N − η, we cannot have r = p. Thus, in all possible cases, we find that p ≡ ±1 (mod 3^{n}) and since p is odd, we have p ≥ 2 · 3^{n} − 1. Since (2 · 3^{n} − 1)^{2} > N, N can only be a prime.

We also note that if N obeys the conditions in the first line of Theorem 29 and N | E_{(N−η)/3}, then N must be a prime.

By extending the results in [2, Chapter 7] it is possible to select the parameters of S_{1}, S_{2} to make Theorem 29 both a necessary and sufficient test for the primality of N, but this test is much less efficient than one based on the Lucas Functions.

In [3, §9] several primality tests for N are presented. These tests can be easily proved by using the techniques in [2, Chapter 7], but to be usable they require that we know the complete factorization of

N^{2} + N + 1 or N^{2} − N + 1.

Of course, such a circumstance is very unlikely, but we might have a partial factorization of N^{2} ± N + 1. In what follows we will devise a test for the primality of N in this case. We first require a simple lemma.

Lemma 30. If p and q are distinct primes, p > 3 and p | D_{qn} and p | U_{qn}/U_{n}, then q^{λ+1} | ω, where ω is the rank of apparition of p in {D_{n}} and q^{λ} || n.

Proof. Suppose p | D_{n}. If p | U_{qn}/U_{n}, then by Theorem 8, we get p | 2q^{3}, which is impossible. Hence, p ∤ D_{n}. It follows that since p | D_{qn} ({D_{n}} is a divisibility sequence), we get ω | qn and ω ∤ n, which means that q^{λ+1} | ω.

We will also need the easily established technical lemma below.

Lemma 31. If x ≥ 5, then

(x^{2} + x + 1)^{2} < 2(x^{4} − x^{2} + 1).

Theorem 32. Let N be a positive integer such that gcd(N, 6) = 1 and put η = 1 or −1. Let T = N^{2} + ηN + 1 and suppose that T′ | T, where gcd(T′, T/T′) = 1 and T^{′2} > 2T. If N | D_{T} and N | U_{T} /U_{T/q} for all distinct primes q such that q | T′, then N is a prime.

Proof. Let p be any prime divisor of N and q be any prime divisor of T′; then p ≥ 5 and by Lemma 30 we have q^{λ} | ω(p), where ω(p) is the rank of apparition of p in {D_{n}} and q^{λ} || T. Since gcd(T′, T/T′) = 1, we have q^{λ} || T′; hence, T′ | ω(p). Let ω denote the rank of apparition of T in {D_{n}}. We have ω | T and ω/q ∤ T; hence, q^{λ} | ω, where q^{λ} || T and therefore T′ | ω.

By (17), we have

ω = lcm(ω(p_{i}^{α_{i}}) : i = 1, 2, …, j),

where

N = ∏_{i=1}^{j} p_{i}^{α_{i}}

is the prime power factorization of N. Since ω(p_{i}^{α_{i}}) = p_{i}^{ν_{i}}ω(p_{i}), we must have ν_{i} = 1 because p_{i} ∤ T. We get

ω = lcm(ω(p_{i}) : i = 1, 2, …, j_{|}T′ ∏_{i=1}^{j} \frac{ω(p_{i})}{T′}.

If we put T = kω, then

T ≤ kT′ ∏_{i=1}^{j} \frac{ω(p_{i})}{T′} ≤ kT′ ∏_{i=1}^{j} \frac{p_{i}^{2} + p_{i} + 1}{T′}

by Theorem 13. Also, since

T = N^{2} + ηN + 1 > 2 ∏_{i=1}^{j} \frac{p_{i}^{2} + p_{i} + 1}{2},

([3, Lemma 9.11], cf. [2, Lemma 7.1]) we get

kT′ ∏_{i=1}^{j} \frac{p_{i}^{2} + p_{i} + 1}{T′} > 2 ∏_{i=1}^{j} \frac{p_{i}^{2} + p_{i} + 1}{2}

and

kT′2^{j} > 2(T′)^{j}.

Hence,

k > (T′/2)^{j−1} ≥ T′/2 (when j ≥ 2).

But since T/T′ = kω/T′, we have k ≤ T/T′ < T′/2, a contradiction; consequently, we can only have j = 1 and N = p^{α}. Since ω(N) = p^{ν}ω(p) and gcd(p, ω(N)) = 1, we get ω(p^{α}) = ω(p). It follows that

ω(N) = ω(p) ≤ p^{2} + p + 1.

Now T′ | ω(p) means that ω(p) ≥ T′ and p^{2} + p + 1 ≥ T′. Since T^{′2} > 2T, we have for α ≥ 2

(p^{2} + p + 1)^{2} > 2(p^{2α} + ηp^{α} + 1) ≥ 2(p^{2α} − p^{α} + 1) ≥ 2(p^{4} − p^{2} + 1)

which is impossible by Lemma 31. Hence we can only have N = p.

Many other primality tests can be devised by making use of the ideas in [2, Chapter 7], but the above should suffice to illustrate the kind of results that can be established.

7 Conclusions

In [3] we showed that the {U_{n}} and {W_{n}} sequences can be considered respectively as the sextic analogues of Lucas’ {u_{n}} and {v_{n}} sequences. In this paper we have produced a number of results that are the number-theoretic analogues of well-known properties of the Lucas functions. Of course, there are many other properties of {D_{n}} and {E_{n}} that are similar to those of the {D_{n}} and {E_{n}} sequences discussed at some length in [2], and these can be proved by using the results presented here and the techniques of [2].

References

[1] S. Müller, H. C. Williams, and E. Roettger, A cubic extension of the Lucas functions, Ann. Sci. Math. Québec 33 (2009), 185–224.

[2] E. Roettger, A Cubic Extension of the Lucas Functions, PhD thesis, University of Cal-

   gary, 2009. Available online at http://people.ucalgary.ca/~williams/.

[3] E. L. Roettger, H. C. Williams, and R. K. Guy, Some extensions of the Lucas functions. In Number Theory and Related Fields, Springer, 2013, pp. 279–319.

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

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

Received February 5 2015; revised version received May 11 2015; May 29 2015. Published in Journal of Integer Sequences, May 30 2015.

Return to Journal of Integer Sequences home page.