A Sextic Extension of the Lucas Functions

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

               williams@math.ucalgary.ca

Abstract

We develop a necessary and sufficient primality test for integers N such that N^{6} −1 is divisible by a large power of 7, based on the properties of two linear recurrence sequences of order 6. These two sequences are analogous to the well-known Lucas sequences. In addition, we provide tables from which it is easy to compute the characteristic polynomial of the sequences.

1 Introduction

Consider the sequence (G_{n}), where G_{0} = 0, G_{1} = 1 and G_{n+1} = G_{n} − 7G_{n−1} for all n ≥ 1. In Table 1 below we tabulate the first few terms of (G_{n}), together with their prime factorizations.

n G_{n}  n G_{n}
0 0  13 −93911
1 1  14 146329 = 41 · 43 · 83
2 1  15 803706 = 2 · 3 · 29 · 31 · 149
3 −6 = −2 · 3  16 −220597 = −13 · 71 · 239
4 −13  17 −5846539
5 29  18 −4302360 = −2^{3} · 3^{2} · 5 · 19 · 629
6 120 = 2^{3} · 3 · 5  19 36623413 = 113 · 324101
7 −83  20 66739933 = 13 · 29 · 211 · 839
8 −923 = −13 · 71  21 −189623958 = −2 · 3 · 83 · 503 · 757
9 −342 = −2 · 3^{2} · 19  22 −656803489 = −8513 · 77153
10 6119 = 29 · 211  23 670564217 = 139 · 4824203
11 8513  24 5268188640 = 2^{5} · 3 · 5 · 11 · 13 · 23 · 47 · 71
12 −34320 = −2^{4} · 3 · 5 · 11 · 13 25 574239121 = 29 · 449 · 44101

Table 1: First few values of the sequence (G_{n}) and their factorizations.

Notice that the terms with subscript divisible by 3 tend to have a lot of small prime factors belonging to no particular residue classes, but the other terms seem only to be divisible by primes that are congruent to ±1 modulo 14. In fact, it can be shown that this is always the case for (G_{n}). This explains why terms with index a multiple of 3 will tend to be highly composite; for all the primes ≢ ±1 (mod 14), two thirds of them must wait until 3 divides n in order to divide some G_{n}.

If we let q be a prime such that q ≡ 1 (mod 3), it is well known that there exist integers x and y such that 4q = x^{2} + 27y^{2}. See, for example, Ireland and Rosen [7, §6 of Chapter 9] or Cox [5, Chapter 4]. Put Q = q and P = x and define the Lucas sequence (U_{n}) by U_{0} = 0, U_{1} = 1 and U_{n+1} = P U_{n} − QU_{n−1} for n ≥ 0. By a special case (p = 3) of Williams [20, Corollary 11.2.4] we have the following result:

Theorem 1. Let q be a prime such that q ≡ 1 (mod 3). Put P = x and Q = q, where 4q = x^{2} + 27y^{2}. If r is a prime such that r ∤ 3qy, r | U_{n} and 3 ∤ n, then r must be a cubic residue of q.

We see, then, that for q = 7 (x = 1 and y = 1), it follows that (U_{n}) = (G_{n}) and every prime divisor r of G_{n} when 3 ∤ n must be a cubic residue of 7. Since the only cubic residues of 7 are ±1, we must have r ≡ ±1 (mod 14).

The Lucas sequences are examples of linear recurrence sequences of order 2; the purpose of this paper is to find extensions of Lucas’ sequences of order greater than 2, which possess properties analogous to those that we have observed in (G_{n}). We then use these sequences to develop primality tests for certain numbers of special form.

2 The Lucas sequences and their extensions

Let P and Q be coprime integers and α, β be the roots of the quadratic polynomial f(x) = x^{2} − P x + Q with δ = α − β and D = δ^{2} = P^{2} − 4Q. We define the Lucas sequences (U_{n}) and (V_{n}) as follows:

U_{n} = (α^{n} − β^{n})/δ,  V_{n} = α^{n} + β^{n}.

Since both U_{n} and V_{n} are symmetric functions of the roots of a polynomial with integer coefficients they must both be integers for all non-negative integral values of n. Also, both (U_{n}) and (V_{n}) satisfy the following second-order linear recurrence:

X_{n+1} = P X_{n} − QX_{n−1},

with U_{0} = 0, U_{1} = 1 and V_{0} = 2, V_{1} = P. The Lucas sequences have many interesting properties that have been applied to many problems; some books that include one or several sections devoted to these sequence, particularly as they apply to primality testing, are Bressoud and Wagon [3], Crandall and Pomerance [6], Ribenboim [11] and Williams [20].

Lucas first applied these sequences to the problem of primality testing of Mersenne numbers; see [20, §5.1 and 5.4]. Indeed, he was actually able to prove the well-known Lucas-Lehmer criterion for the primality of M_{n} = 2^{n}−1. This test is both a necessary and sufficient condition for M_{n} to be a prime number. Lucas also considered, for a fixed value of A, the more general N_{n} = A2^{n} − 1, and provided a sufficiency test for N_{n} to be a prime. For some commentary on this work, see Roettger, Williams and Guy [15]. It was Lehmer [8] who essentially proved the following result:

Theorem 2. Let N_{n} = A2^{n} − 1, where n > 1, A is odd and A < 2^{n}. If P and Q are selected such that the Jacobi symbols (D/N_{n}) = (Q/N_{n}) = −1, then N_{n} is a prime if and only if N_{n} | V_{(N_{n}+1)/2}.

This result can be modified slightly, as follows.

Theorem 3. Let N_{n} = A2^{n} − 1, where n > 1, A is odd and A < 2^{n}. Let q be a prime such that q ≡ 1 (mod 4) and the Legendre symbol (N_{n}/q) = −1. If x and y are integers such that q = x^{2} + y^{2}, put P = 2x, Q = q; then N_{n} is a prime if and only if N_{n} | V_{(N_{n}+1)/2}.

In the case that N_{n} = A3^{n} −1, results in Williams [19] can be used to prove the following analogue of Theorem 3.

Theorem 4. Let N_{n} = A3^{n} − 1, where n > 1, 3 ∤ A and A < 3^{n}. Suppose q is a prime congruent to 1 modulo 3 such that N_{n}^{(q−1)/3} ≢ 1 (mod q) and 4q = x^{2} + 27y^{2}. Put P = x and Q = q. If gcd(N_{n}, qy) = 1, then N_{n} is a prime if and only if V_{2θ} ≡ −Q^{θ} (mod N_{n}), where θ = (N_{n} + 1)/3.

We say that a sequence of integers (X_{n}) is a divisibility sequence if whenever X_{n} ≠ 0, we have X_{n} | X_{mn} for all non-negative integers n and m. For example, (n) is trivially a divisibility sequence, but so are (G_{n}) and the Mersenne sequence (M_{n}). Lucas made much use of the fact that (U_{n}) is always a divisibility sequence.

Let the sequence (X_{n}) be determined by an initial set of h integer values

X_{0}, X_{1}, X_{2}, …, X_{h−1}  (1)

and the h^{th} order linear recurrence

X_{n+h} = P_{1}X_{n+h−1} − P_{2}X_{n+h−2} + ⋯ + (−1)^{h−1}P_{h}X_{n},  (2)

where P_{1}, P_{2},…, P_{h} are given fixed integers. Notice that the values for X_{n} for all n ≥ 0 are completely determined by (1) and (2). We define the characteristic polynomial f(x) of the linear recurrence sequence (X_{n}) to be

f(x) = x^{h} − P_{1}x^{h−1} + P_{2}x^{h−2} − ⋯ + (−1)^{h}P_{h}.  (3)

Lucas speculated that his sequences might be extended to those that satisfy a linear recurrence sequence of order greater than 2. Indeed, it is argued in Roettger, Williams and Guy [14] that the Lucas sequences are characterized by five basic properties:

(1) There are two sequences of integers (when n ≥ 0).

(2) Both sequences satisfy the same linear recurrence relation.

(3) One of the two sequences is a divisibility sequence.

(4) There are addition formulas for the terms of the sequences.

(5) There are multiplication formulas for the terms of the sequences.

Given what we know about Lucas’ unsuccessful attempt to generalize his sequences, it seems that every sequence that he might have found acceptable as a proper generalization of (U_{n}) and (V_{n}) should possess these five properties.

In [14] the authors proposed generalizing Lucas’ sequence to

U_{n} = λ^{n−1} ∏_{i=1}^{k}(1 − γ_{i}^{n})/(1 − γ_{i})  and  V_{n} = λ^{n} ∏_{i=1}^{k}(1 + γ_{i}^{n}),  (4)

where λ and γ_{1}, γ_{2}, …, γ_{k} are simply constrained to be distinct non- zero algebraic numbers such that V_{1} ≠ 0 and both (U_{n}), (V_{n}) are sequences of integers for n ≥ 0. Notice that, just as in the case of the Lucas sequences, we have V_{n} = U_{2n}/U_{n}.

Under the above constraints it is easy to prove that if k = 1, P = λ(γ_{1}+1), Q = λ^{2}γ_{1}, then both P and Q must be integers because V_{1} = λ(γ_{1} +1), V_{2} = λ^{2}(1+γ_{1}^{2}), U_{3} = λ^{2}(1+γ_{1} +γ_{1}^{2}) are all integers. In this case, we see that in (4) U_{n} = U_{n}(P, Q), V_{n} = V_{n}(P, Q), where α = λ and β = λγ_{1}. Thus, (4) represents a generalization of the Lucas functions.

For a fixed value of k, conditions on λ and γ_{1}, γ_{2}, …, γ_{k} were derived in [14] to ensure that both (U_{n}) and (V_{n}) are sequences of integers that satisfy the same linear recurrence. For example, one of these conditions is that Q = λ^{2}γ_{1}γ_{2} ⋯ γ_{k} be a rational integer. It is also shown that under these same conditions (U_{n}) is a divisibility sequence. In the case that k = 2, we must have T_{1}, T_{2} and Q integers, where

T_{1} = λ(1 + γ_{1})(1 + γ_{2}),  T_{2} = λ^{2}(γ_{1} + γ_{2})(1 + γ_{1}γ_{2}) + 2λ^{2}γ_{1}γ_{2},  Q = λ^{2}γ_{1}γ_{2}.

Thus, if we put P_{1} = T_{1} and P_{2} + 2Q = T_{2}, we must have P_{1}, P_{2} and Q integers. In this case we find that both (U_{n}) and (V_{n}) satisfy the same fourth-order linear recurrence:

X_{n+4} = P_{1}X_{n+3} − (P_{2} + 2Q)X_{n+2} + P_{1}QX_{n+1} − Q^{2}X_{n},  (5)

with initial conditions U_{0} = 0, U_{1} = 1, U_{2} = P_{1}, U_{3} = P_{1}^{2} − P_{2} − 3Q, V_{0} = 4, V_{1} = P_{1}, V_{2} = P_{1}^{2} − 2P_{2} − 4Q, V_{3} = P_{1}(P_{1}^{2} − 3P_{2} − 3Q). Indeed, it has been shown by Abrate et al. [1] that if (X_{n}) is a linear recurrence sequence of order four that is nondegenerate (no quotient of any two of the roots of the characteristic polynomial is a root of unity) and a divisibility sequence, then (X_{n}) must satisfy a linear recurrence of the form (5) for some integers P_{1}, P_{2} and Q.

The above sequences, denoted here by (U_{n}) and (V_{n}), were discussed in some detail by Williams and Guy in [21] and in greater detail in [15]. Suffice it to say here that they possess the five properties of the Lucas sequences mentioned above; furthermore, they also enjoy many of the arithmetic properties of the Lucas sequences. Thus, these are evidently the fourth-order analogs of the Lucas sequences.

As in [15, §7], let q be a prime such that q ≡ 1 (mod 5) and define in (5)

P_{1} = P (1, 5, q),  P_{2} = P (2, 5, q),  Q = q^{3},  (6)

where the rational integers P (i, 5, q) are defined in [20, (11.1.5)]. As indicated by the notation, the values of P_{1}, P_{2} and Q here depend only on the value of q. Notice that when k = 2 in [20, §10.1], the functions denoted by symbols C_{n} and V_{1,n} there are the same except possibly for sign; also U_{n} = V_{1,n} = ±C_{n}. If we let D here denote the discriminant of the characteristic polynomial of (U_{n}), we have the following consequence of [20, Corollary 11.2.5]:

Theorem 5. Suppose P_{1}, P_{2} and Q are given by (6). If r is a prime such that r ∤ 5qD, r | U_{n} and 5 ∤ n, then r must be a quintic residue of q.

This result is for the extended Lucas sequence (U_{n}) above exactly analogous to the case of the Lucas sequence of Theorem 1. In the case of q = 11, we have P_{1} = P (1, 5, q) = −89, P_{2} = P (2, 5, q) = 1199. The prime factorizations of the values of the corresponding U_{n} for n = 0, 1, …, 30 are provided in [20, Table 11.2.1]. The behaviour of these factorizations is similar to the corresponding case of (G_{n}), but more extreme because only two of the 10 nonzero residues of 11 are quintic resides of 11.

Let η = ±1. If a is an odd integer, define m(a) by m(a) = (a−η)/5 when a ≡ η (mod 5); otherwise put m(a) = (a^{2} + 1)/5 . Also, as in [15], let γ_{n}(5) denote the odd solution x of x^{2} + 1 ≡ 0 (mod 5^{n}) such that 0 < x < 5^{n}. Set

N_{n} = A5^{n} + η  or  N_{n} = A5^{n} + ηγ_{n}(5).  (7)

By using the methods of [15, §7] it is possible to prove the following analogue of Theorem 4.

Theorem 6. Let N_{n} be given by (7), where A is even, γ_{n}(5) ∤ A, and A < 2 · 5^{n}. Suppose that q is a prime congruent to 1 modulo 5 such that N_{n}^{(q−1)/5} ≢ 1 (mod q) and let P_{1}, P_{2}, and Q be given by (6), Δ = P_{1}^{2} − 4P_{2}, and m = m(N_{n}). If gcd(N_{n}, qD) = 1, then N_{n} is a prime if and only if

V_{m} ≡ −Q^{m/2} (mod N_{n})  and  ΔU_{m}^{2} ≡ 5Q^{m} (mod N_{n}).

3 Some sixth-order divisibility sequences

We say that a linear recurring sequence of order k that is also a divisibility sequence is a linear divisibility sequence (LDS) of order k. We have already discussed some properties of certain LDSs of order 2 and 4. In this section we discuss some sixth-order LDSs that can be derived from (4). Much more concerning this can be found in [14].

When k = 3, the situation in (4) is somewhat more complicated than in the cases of k = 1, 2 because the corresponding (U_{n}) and (V_{n}) sequences satisfy a linear recurrence of order 8, given in [14, Theorem 5.3]. A difficulty arises when we try to develop the addition and multiplication formulas because it becomes necessary to introduce a third sequence in order to do this; thus, the sequences when k = 3 cannot in general satisfy the five conditions given earlier. This, of course is also likely the case for k > 3. Nevertheless, there is a special case when k = 3 that does allow us to require only two sequences; this is the case when γ_{1}γ_{2}γ_{3} = 1. Here we must have λ an integer, denoted by R, and the resulting sequences (U_{n}) and (V_{n} − 2R^{n}) satisfy the same linear recurrence of order 6:

X_{n+6} = S_{1}X_{n+5} − (S_{2} + 3R^{2})X_{n+4} + (S_{3} + 2R^{2}S_{1})X_{n+3} − R^{2}(S_{2} + 3R^{2})X_{n+2} + R^{4}S_{1}X_{n+1} − R^{6}X_{n}, (8)

where S_{1}, S_{2}, and S_{3} are integers such that

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

Let G(x) be the characteristic polynomial of (8). In this case it turns out that ρ_{1}, ρ_{2}, ρ_{3}, where ρ_{i} = R(γ_{i} + γ_{i}^{−1}) (i = 1, 2, 3), are the roots of the cubic polynomial

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

If we put W_{n} = V_{n} − 2R^{n}, it is shown in [14] that (U_{n}) is a divisibility sequence and the two sequences (U_{n}), (W_{n}) also possess the five properties mentioned in the previous section and we call them the extended Lucas sequences for k = 3.

We find that

U_{0} = 0, U_{1} = 1, U_{2} = S_{1} + 2R, U_{3} = S_{1}^{2} + RS_{1} − S_{2} − 3R^{2};  (10)
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, for every integer n we have

U_{−n} = −U_{n}/R^{2n}  and  W_{−n} = W_{n}/R^{2n}.  (11)

Suppose we are given integral values for S_{1} (≠ −2R), S_{2}, and determine S_{3} by (9). We know by [14, Theorem 7.2] that if (U_{n}), (W_{n}) satisfy the linear recurrence (8) with initial conditions given by (10) and subject to (11) for n = 1 and 2, then there must exist algebraic numbers γ_{1}, γ_{2}, γ_{3} with γ_{1}γ_{2}γ_{3} = 1 such that U_{n} and V_{n} = W_{n} + 2R^{n} are given by (4).

Some examples of the sixth-order LDS (U_{n}) can be found in the On-line Encyclopedia of Integer Sequences (OEIS) [16]; in particular, we mention \underline{A180510} with S_{1} = −1, S_{2} = −5, S_{3} = 7, R = 1, and \underline{A005120} with S_{1} = −3, S_{2} = 2, S_{3} = 1, R = 1. Others are \underline{A001351}, \underline{A001945} and \underline{A006235}.

Many arithmetic properties of the extended Lucas sequences (U_{n}), (W_{n}) when gcd(S_{1}, S_{2}, R) = 1 are provided in [14, 13]. These are very similar to corresponding results involving the standard Lucas sequences. If we put

Δ = R^{2}(1 − γ_{1})^{2}(1 − γ_{2})^{2}(1 − γ_{3})^{2},

we find that Δ is the discriminant of g(x) and we can write

Δ = S_{1}^{2} − 4S_{2} + 4RS_{1} − 12R^{2}.

Also, if

Γ = R^{4}(γ_{1} − γ_{2})^{2}(γ_{2} − γ_{3})^{2}(γ_{3} − γ_{1})^{2},  (12)

we have

Γ = 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}.

Now assume that λ_{i} (i = 1, 2, …, 6) are distinct algebraic integers such that

λ_{1}λ_{2} = λ_{3}λ_{4} = λ_{5}λ_{6} = R^{2},  (13)

where R is a rational integer. Assume, in addition, that

λ_{1}λ_{3} = Rλ_{6},  λ_{1}λ_{5} = Rλ_{4},  λ_{2}λ_{4} = Rλ_{5},  (14)
λ_{2}λ_{6} = Rλ_{3},  λ_{3}λ_{5} = Rλ_{2},  λ_{4}λ_{6} = Rλ_{1}.

Proposition 7. Suppose that λ_{i} (i = 1, 2, …, 6) satisfy the conditions (13) and (14). If we put ρ_{1} = λ_{1} + λ_{2}, ρ_{2} = λ_{3} + λ_{4}, ρ_{3} = λ_{5} + λ_{6}, then ρ_{1}, ρ_{2}, ρ_{3} are the roots of a cubic g(x) = x^{3} − S_{1}x^{2} + S_{2}x − S_{3} with integral coefficients satisfying (9) if and only if μ = λ_{1} + λ_{3} + λ_{5}, ν = λ_{2} + λ_{4} + λ_{6} are the roots of a quadratic polynomial x^{2} − T_{1}x + T_{2} with integral coefficients.

Proof. Follows easily from the following identities:

ρ_{1} + ρ_{2} + ρ_{3} = μ + ν,  ρ_{1}ρ_{2} + ρ_{2}ρ_{3} + ρ_{3}ρ_{1} = R(μ + ν) + μν − 3R^{2}
and  ρ_{1}ρ_{2}ρ_{3} = R(μ + ν)^{2} − 2R^{2}(μ + ν) − 2Rμν + 2R^{3}.

The latter two of these can be easily verified by appealing to (13) and (14).

We note that under the above conditions each λ_{i} (i = 1, 2, …, 6) is a root of

G(x) = 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} = 0.

We next put μ_{n} = λ_{1}^{n} + λ_{3}^{n} + λ_{5}^{n}, ν_{n} = λ_{2}^{n} + λ_{4}^{n} + λ_{6}^{n}; since by (13) and (14) we find that λ_{1}λ_{3}λ_{5} = λ_{2}λ_{4}λ_{6} = R^{3},

(λ_{1}^{n} − R^{n})(λ_{3}^{n} − R^{n})(λ_{5}^{n} − R^{n}) = R^{2n}(μ_{n} − ν_{n}),  (15)
(λ_{2}^{n} − R^{n})(λ_{4}^{n} − R^{n})(λ_{6}^{n} − R^{n}) = −R^{2n}(μ_{n} − ν_{n}).

Note that if we put δ = μ_{1} − ν_{1}, then because the λ_{i} (i = 1, 2, …, 6) are all distinct, we conclude from (15) and (13) that δ ≠ 0. In fact, Δ = δ^{2} is the discriminant of g(x) = x^{3} − S_{1}x^{2} + S_{2}x − S_{3}. We now define

U_{n} = (μ_{n} − ν_{n})/(μ_{1} − ν_{1});

then

U_{0} = 0, U_{1} = 1, U_{2} = μ_{1} + ν_{1} + 2R = S_{1} + 2R,
U_{3} = (μ_{1} + ν_{1})^{2} − μ_{1}ν_{1} = S_{1}^{2} + RS_{1} − S_{2} − 3R^{2}.

Also, it is easy to see from (13) that

λ_{1}^{−n} = λ_{2}^{n}/R^{2n},  λ_{3}^{−n} = λ_{4}^{n}/R^{2n},  λ_{5}^{−n} = λ_{6}^{n}/R^{2n};

hence, by (15) we get U_{−n} = −U_{n}/R^{2n}. It follows that (U_{n}) must be a sixth-order LDS with characteristic polynomial G(x). If we put γ_{1} = λ_{1}/R, γ_{2} = λ_{3}/R, γ_{3} = λ_{5}/R, then by (15) we get U_{n} and V_{n} (= μ_{n} + ν_{n} + 2R^{n}) given by (4) with γ_{1}γ_{2}γ_{3} = 1. Thus, if W_{n} = V_{n} − 2R^{n} = μ_{n} + ν_{n}, we see that (U_{n}) and (W_{n}) are the extended Lucas sequences when k = 3.

We conclude this section with some number-theoretic properties of the k = 3 extended Lucas sequence (U_{n}). Let m be an integer. We define the ranks of apparition ψ_{1}, ψ_{2},… of m in (U_{n}) as follows: let ψ_{1} (if it exists) be the least positive value of n such that m | U_{n}. For i = 1, 2, … define ψ_{i+1} (if it exists) to be the least positive integer such that m | U_{n} for n = ψ_{i+1} and ψ_{j} ∤ ψ_{i+1} for all j such that 1 ≤ j ≤ i. From results in [14, §9] we have the following theorems.

Theorem 8. Suppose that r is a prime such that r ∤ 6ΔΓR and let ϵ be the value of the Legendre symbol (Δ/r). If r has more than one rank of apparition in (U_{n}), then these ranks must all be divisors of r − ϵ. Furthermore, if r has a single rank of apparition in (U_{n}), it must be a divisor of either r − ϵ or r^{2} + ϵr + 1.

Theorem 9. Suppose that r is a prime such that r ∤ 6ΔΓR. If r is a divisor of some term U_{n} (n ≠ 0) of the sequence (U_{n}) then some rank of apparition of r in (U_{n}) must divide n.

4 Some arithmetic properties of the k = 3 extended Lucas sequences

For n ≥ 1, define D_{n} = gcd(W_{n} − 6R^{n}, U_{n}); by [13, Theorem 4] we know that (D_{n}) is a divisibility sequence. Let ω be the least positive value of n, if it exists, such that m divides the term D_{n} of the sequence (D_{n}) we call ω the rank of apparition of m in (D_{n}). We next present some additional arithmetic results concerning (D_{n}).

Theorem 10. ([13, Theorem 14]) If r is a prime such that r ∤ 2R, there exists a rank of apparition ω of r in (D_{n}); furthermore, if r divides any term D_{m} of (D_{n}), then ω must divide m.

Theorem 11. Suppose that r is a prime such that r ∤ 2R and let ϵ be the value of the Legendre symbol (Δ|r). The rank of apparition of r in (D_{n}) is either a divisor of r, r^{2} − 1 or of r^{2} + ϵr + 1.

Proof. Follows from the previous result and [13, Theorems 9 and 13].

We also have some results that can be applied to the problem of primality testing.

Lemma 12. Let N be a positive integer such that gcd(N, 2R) = 1 and n be a positive integer such that gcd(N, n) = 1. If m is a positive integer such that N | U_{mn}/U_{m}, then gcd(N, D_{m}) = 1.

Proof. By [13, Theorem 8] we know that gcd(U_{mn}/U_{m}, D_{m}) must be a divisor of 2n^{3}. The result now follows easily because gcd(N, 2n) = 1.

We can now prove a theorem analogous to [15, Theorem 2.4].

Theorem 13. Let N be a positive integer such that gcd(N, 2R) = 1. Suppose that n is a positive integer such that gcd(N, n) = 1 and that for some positive integer m we have N | D_{mn} and N | U_{mn}/U_{m}. If r is a prime divisor of N and ω(r) is its rank of apparition in (D_{n}), then ω(r) | mn and ω(r) ∤ m.

Proof. Clearly, by Theorem 10 we must have ω(r) | mn, because r | D_{mn}. Also, by Lemma 12, we see that r cannot divide D_{m}; hence, ω(r) ∤ m.

We next examine some values for N to which these results can be applied. Let p be an odd prime such that p ≡ 1 (mod 3) and let λ_{n}(p) be the least value of x such that

x^{2} + x + 1 ≡ 0 (mod p^{n}) and 1 < x < p^{n}.

If we let Y_{n}(p) denote the set of all six distinct solutions of

x^{6} − 1 = (x^{2} − 1)(x^{2} + x + 1)(x^{2} − x + 1) ≡ 0 (mod p^{n}),  (16)

it is easy to see that if y = λ_{n}(p), then Y_{n}(p) ≡ {±1, ±y, ±y^{2}} (mod p^{n}); thus,

Γ_{n}(p) = {1, p^{n} − 1, λ_{n}(p), p^{n} − 1 − λ_{n}(p), p^{n} − λ_{n}(p), 1 + λ_{n}(p)}

is the set of all six solutions x of (16) such that 1 ≤ x < p^{n}. Also, Y_{n}(p) is a group under the operation of multiplication modulo p^{n}. Let γ_{n}(p) ∈ Γ_{n}(p) and put

N_{n} = Ap^{n} + γ_{n}(p)  (17)

for some fixed positive integer A and n > 1. In what follows we will develop a technique that is sufficient for determining whether N_{n} is a prime.

We first observe that there are only two elements of Γ_{n}(p) that are both bigger than 1 and odd; denote them by β_{n}(p) and β_{n}^{∗}(p) and note that β_{n}(p) + β_{n}^{∗}(p) = p^{n} ± 1. If either β_{n}(p) or β_{n}^{∗}(p) is a divisor of N_{n}, then since both exceed 1 and are less than p^{n} (< N_{n}), N_{n} cannot be a prime. We now establish the lemma below.

Lemma 14. Let odd N_{n} be given by (17), where n > 1, A < 2p^{n}, and β_{n}(p), β_{n}^{∗}(p) do not divide N_{n}, and N_{n} is not a perfect square. If N_{n} has at least one prime divisor t ≡ γ (mod p^{n}), where γ ∈ Γ_{n}(p), then N_{n} must be a prime.

Proof. If N_{n} is composite, then N_{n} = tT, where T > 1. We have γT ≡ γ_{n}(p) (mod p^{n}); hence, T ≡ γ^{∗} (mod p^{n}), where γ^{∗} ∈ Γ_{n}(p). Thus, there exist integers m_{1} and m_{2} such that

Ap^{n} + γ_{n}(p) = N_{n} = (m_{1}p^{n} + γ)(m_{2}p^{n} + γ^{∗}).  (18)

Since both t and T exceed 1 and neither γ nor γ^{∗} divides N_{n}, we could only have m_{1} or m_{2} = 0 whenever the corresponding γ or γ^{∗} is even, but this is impossible because both t and T are odd. It follows that m_{1}m_{2} ≥ 1. If m_{1}m_{2} ≥ 2, then by (18) we have N_{n} ≥ (p^{n} + 1)(2p^{n} + 1) > 2p^{2n} + γ_{n}(p), which means that A > 2p^{n}, a contradiction. Thus, we can only have m_{1} = m_{2} = 1. In this event both γ and γ^{∗} must be even. If γ = γ^{∗}, we see that N_{n} a perfect integral square, which is not permitted. If γ and γ^{∗} are distinct, then because γ, γ^{∗} ∈ Γ_{n}(p) and are both even, we have γ + γ^{∗} ≥ p^{n} − 1 and therefore one of γ or γ^{∗} must exceed or equal (p^{n} − 1)/2. Also, since p^{n} cannot divide 2^{6}, we observe that 2 ∉ Γ_{n}(p); thus, both γ and γ^{∗} must be at least 4. We then have γγ^{∗} ≥ 2(p^{n} − 1) > γ_{n}(p). By (18) we get Ap^{n} > p^{2n} + p^{n}(p^{n} − 1) = 2p^{2n} − p^{n}, and consequently A > 2p^{n} − 1, which is also a contradiction.

In general, the determination of whether or not a given integer is a perfect square can be done quite easily, but in the above case it is even easier because if N_{n} is a perfect square, then N_{n} = (p^{n} + γ)^{2}, where γ ∈ Γ_{n}(p) and 2 | γ. As we must have γ^{2} ≡ γ_{n}(p) (mod p^{n}) and 2 | γ, we can only have γ = p^{n} − 1 when γ_{n}(p) = 1. However, in this case we find that N_{n} = (2p^{n} − 1)^{2}, which since A < 2p^{n}, is impossible. Now it is easy to show that if γ ∈ Γ_{n}(p) and γ^{2} ≢ 1 (mod p^{n}), then γ^{2} ≡ λ_{n}(p) or γ^{2} ≡ p^{n} − λ_{n}(p) − 1 (mod p^{n}). Thus, the only remaining possibilities for γ_{n}(p) are either λ_{n}(p) or p^{n} − λ_{n}(p) − 1 and in either case γ_{n}(p)^{2} + γ_{n}(p) + 1 ≡ 0 (mod p^{n}). Also, for each of these possibilities the corresponding γ is either γ_{n}(p) + 1 or p^{n} − γ_{n}(p) − 1. If we put κ_{n}(p) = (γ_{n}(p)^{2} + γ_{n}(p) + 1)/p^{n}, we see that N_{n} = (p^{n} + γ)^{2} only if A = p^{n} + 2(γ_{n}(p) + 1) + κ_{n}(p) or A = 4p^{n} − 4(γ_{n}(p) + 1) + κ_{n}(p). Thus, we can exclude the possibility that N_{n} is a perfect square in Lemma 14 if we assert that

A ≠ p^{n} + 2(γ_{n}(p) + 1) + κ_{n}(p) when 2 | A or  (19)
A ≠ 4p^{n} − 4(γ_{n}(p) + 1) + κ_{n}(p) when 2 | A.

Notice that if

A = p^{n} + 2(γ_{n}(p) + 1) + κ_{n}(p) or
A = 4p^{n} − 4(γ_{n}(p) + 1) + κ_{n}(p),

then N_{n} is a perfect square and therefore cannot be a prime.

With the above results we can now devise a sufficiency test for the primality of N_{n}.

Theorem 15. Let odd N_{n} be given by (17), where n > 1, A < 2p^{n}, A satisfies (19), and β_{n}(p), β_{n}^{∗}(p) do not divide N_{n}. Suppose gcd(N_{n}, R) = 1 and m is some positive integer such that p^{n−1} | m. If N_{n} | D_{mp} and N_{n} | U_{mp}/U_{m}, then N_{n} is a prime.

Proof. Let r be a prime divisor of N_{n}, and let ω(r) denote its rank of apparition in (D_{n}). By Theorem 13, we must have ω(r) | mp and ω(r) ∤ m; hence, p^{n} | ω(r). Since gcd(p, N_{n}) = 1, we see that p ≠ r. Thus, by Theorem 11, we must have t ≡ γ (mod p^{n}), where γ ∈ Γ_{n}(p); it follows by Lemma 14 that N_{n} is a prime.

In order for Theorem 15 to be practical, we need to study how to compute W_{mn} and U_{mn}/U_{m} modulo N for a positive integer N such that gcd(N, R) = 1. Let e_{i}(x_{1}, x_{2}, …, x_{6}) denote the i^{th} elementary symmetric polynomial of x_{1}, x_{2},…, x_{6} and put

A_{i} = e_{i}(λ_{1}^{n}, λ_{2}^{n}, λ_{3}^{n}, …, λ_{6}^{n})

for i = 1, 2, …, 6. If μ_{n} = λ_{1}^{n} + λ_{3}^{n} + λ_{5}^{n}, ν_{n} = λ_{2}^{n} + λ_{4}^{n} + λ_{6}^{n} and (13) and (14) hold, it is not difficult to show that

A_{1} = μ_{n} + ν_{n} = W_{n}, A_{2} = R^{n}(μ_{n} + ν_{n}) + μ_{n}ν_{n},
A_{3} = R^{n}(μ_{n} + ν_{n})^{2} − 2R^{n}μ_{n}ν_{n} + 2R^{3n}

and A_{4} = R^{2n}A_{2}, A_{5} = R^{4n}A_{1}, A_{6} = R^{6n}. Also, since

μ_{n} + ν_{n} = W_{n} and μ_{n} − ν_{n} = δU_{n},

we find that μ_{n}ν_{n} = (W_{n}^{2} − ΔU_{n}^{2})/4; hence,

A_{2} = R^{n}W_{n} + (W_{n}^{2} − ΔU_{n}^{2})/4.

In addition to this we note that since

μ_{2n} + ν_{2n} = (μ_{n} + ν_{n})^{2} − 2μ_{n}ν_{n} − 2R^{n}(μ_{n} + ν_{n})

we get W_{2n} = W_{n}^{2} − 2μ_{n}ν_{n} − 2R^{n}W_{n} and 2μ_{n}ν_{n} = W_{n}^{2} − W_{2n} − 2R^{n}W_{n}. If we substitute this latter formula into the formulas for A_{3} above, we get

A_{3} = R^{n}(W_{2n} + 2R^{n}W_{n} + 2R^{2n}).

Since λ_{i}^{n} (i = 1, 2, …, 6) are the roots of x^{6} − A_{1}x^{5} + A_{2}X^{4} − A_{3}x^{3} + A_{4}x^{2} − A_{5}x + A_{6}, we see that for a fixed n both (W_{h}) and (U_{h}) satisfy the linear recurrence

Z_{mn+6n} = A_{1}Z_{mn+5n} − A_{2}Z_{m+4n} + A_{3}Z_{mn+3n} − R^{2n}A_{2}Z_{mn+2n} + R^{4n}A_{1}Z_{mn+n} − R^{6n}Z_{nm}, (20)

a generalization of (8).

Suppose that a given N is such that gcd(N, 2R) = 1. For positive integers n and m define

X_{n} ≡ W_{n}/(2R^{n}), D̃_{n} ≡ ΔU_{n}^{2}/(4R^{2n}),
Y_{n,m} ≡ U_{mn}/(U_{m}R^{mn−m}) (mod N).

If we refer back to Theorem 15, we see that N | D_{mp} and N | U_{mp}/U_{m} if and only if X_{mp} ≡ 3 (mod N) and Y_{p,m} ≡ 0 (mod N).

In view of (20) we can use the arguments made by Roettger and Williams in [12, §3], to compute remote terms of both (U_{n}) and (W_{n}) modulo N. Indeed, there exist polynomials F_{m}, G_{m} ∈ ℤ[x, y] such that

X_{mn} = F_{m}(X_{n}, D̃_{n}) and Y_{m,n} = G_{m}(X_{n}, D̃_{n}).

We have F_{0}(x, y) = 3, F_{1}(x, y) = x, F_{2}(x, y) = x^{2} +y −2x, F_{3}(x, y) = x^{3} +3xy +3y −3x^{2} +3 and G_{0}(x, y) = 0, G_{1}(x, y) = 1, G_{2}(x, y) = 2x + 2, G_{3}(x, y) = 3x^{2} + y. Also, if we define the sextet S_{m} = {F_{m}, F_{m+1}, F_{m+2}, G_{m}, G_{m+1}, G_{m+2}}, then given S_{m}, we can compute S_{2m+1} or S_{2m} in 12 multiplications by using the formulas given in [12]. We remark here that there are some misprints in [12, formulas (14) and (15)]. For our case they should read

F_{2m+3} = F_{m+1}(F_{m+2} − x) + yG_{m+1}(G_{m+2} + 1) + F_{m},
G_{2m+3} = F_{m+1}(G_{m+2} − 1) + G_{m+1}(F_{m+2} + x) − G_{m},

respectively. If we put x ≡ X_{n} and y ≡ D̃_{n} (mod N), this allows us to compute X_{mn} ≡ F_{m}(x, y), Y_{m,n} ≡ G_{m}(x, y) (mod N) in 12k modular multiplications modulo N, where k = ⌈log N⌉.

5 Some results concerning Gaussian and Jacobi sums

In this section we will review some of the properties of some special sums that will be of importance in the sequel. We first consider two distinct odd primes p, q, where q ≡ 1 (mod p). Let χ denote a primitive Dirichlet character of order p. If t is a primitive root of q, we can define χ by χ(t^{j}) = ζ_{p}^{j}, where ζ_{p} is a fixed primitive p^{th} root of unity. It is well known, see, for example, Williams [20, Chapter 11] or Berndt et al. [2], that if τ(χ) denotes the Gauss sum

τ(χ) = ∑_{j=1}^{q−1} χ(j)ζ_{q}^{j},

where ζ_{q} is a primitive q^{th} root of unity, then

τ(χ)τ(χ^{−1}) = q.  (21)

We also know that (τ(χ))^{p}/q can be written as the sum ∑_{i=0}^{p−1} b_{i}ζ_{p}^{j}, where b_{i} ∈ ℤ for i = 0, 1, 2, …, p − 1. In fact, we can write

(τ(χ^{j}))^{p}/q = ∑_{i=0}^{p−1} b_{i}ζ_{p}^{ij}, (j = 1, 2, …, p − 1).  (22)

This is a consequence of the fact that if χ_{1}χ_{2} ≠ χ_{0}, the primitive Dirichlet character, then

τ(χ_{1})τ(χ_{2}) = J(χ_{1}, χ_{2})τ(χ_{1}χ_{2}),  (23)

where J(χ_{1}, χ_{2}) is the Jacobi sum. For much more information on Gaussian and Jacobi sums, see [2]. From (23) and (21), we easily deduce that

J(χ^{m}, χ^{n})J(χ^{−m}, χ^{−n}) = q  (24)

and by [2, Theorem 2.1.5] we have

J(χ^{n}, χ^{m}) = J(χ^{m}, χ^{n}) = J(χ^{−m−n}, χ^{m}) = J(χ^{−m−n}, χ^{n}).  (25)

In [20, §11.1] one method of computing non-negative integers B(i, j) (0 ≤ i, j ≤ p − 1) such that

J(χ, χ^{j}) = ∑_{i=0}^{p−1} B(i, j)ζ_{p}^{i}  (26)

is discussed. There are other methods for computing the B(j, 1); for example, Whiteman [18, (5.8)] has given a general method that involves computing Jacobsthal sums.

In the case of p = 7, several properties of these Dickson-Hurwitz sums B(i, j) are provided in Leonard and Williams [9, 10]. This will be discussed further in §7 below.

By using (24) and

(τ(χ))^{p} = q ∏_{i=1}^{p−2} J(χ, χ^{i}),  (27)

a consequence of (21) and (23), we see that all p values of the integers b_{i} in (22) can be computed in O(p^{3}) arithmetic operations, once the p^{2} values of B(i, j) (0 ≤ i, j ≤ p − 1) have been calculated. Notice that the values of all of these integers depend only on the preselected values of p and q.

Let 𝕂 = ℚ(ζ_{p}) be the cyclotomic field formed by adjoining ζ_{p} to the rationals. These fields have been the objects of much study (see, for example, Washington [17]), but we will only require a few simple results concerning them here. For j not divisible by p, we define the automorphism σ_{j} on 𝕂 by σ_{j}(ζ_{p}) = ζ_{p}^{j}. Note that σ_{j}(J(χ^{m}, χ^{n})) = J(χ^{jm}, χ^{jn}). Let 𝔮 be a prime ideal lying over the principal ideal (q) in the ring O (= ℤ[ζ_{p}]) of algebraic integers in 𝕂. Since q ≡ 1 (mod p), we can write [2, p. 65]

qO = 𝔮_{1}𝔮_{2}𝔮_{3} ⋯ 𝔮_{p−1},

where the 𝔮_{j} (j = 1, 2, …, p − 1) are distinct prime ideals lying over q in O and 𝔮_{j} = σ_{j}(𝔮). With this information, we can use [2, Theorem 2.1.14] to find the prime ideal decomposition of J(χ^{n}, χ^{m}) in 𝕂.

In the sequel we assume p = 7 and denote ζ_{7} by ζ . For fixed j such that 7 ∤ j define

ξ(χ^{j}) = τ(χ^{j})^{7}τ(χ^{5j})^{7}.  (28)

By (27) and (25) we get

τ(χ^{j})^{7} = qJ(χ^{j}, χ^{j})^{2}J(χ^{j}, χ^{2j})^{2}J(χ^{j}, χ^{3j}) and
τ(χ^{5j})^{7} = qJ(χ^{5j}, χ^{5j})^{2}J(χ^{5j}, χ^{3j})^{2}J(χ^{5j}, χ^{j}).

Also, by (25) we have

J(χ^{−j}, χ^{−2j}) = J(χ^{3j}, χ^{−2j}) = J(χ^{3j}, χ^{5j});

hence, by (24) we get

ξ(χ^{j}) = q^{4}J(χ^{j}, χ^{j})^{2}J(χ^{5j}, χ^{5j})^{2}J(χ^{j}, χ^{3j})J(χ^{5j}, χ^{j}),

which since J(χ^{5j}, χ^{j}) = J(χ^{j}, χ^{j}), J(χ^{j}, χ^{3j}) = J(χ^{3j}, χ^{3j}) ( by (25)) means that we can write

ξ(χ^{j}) = q^{4}J(χ^{j}, χ^{j})^{3}J(χ^{5j}, χ^{5j})^{2}J(χ^{3j}, χ^{3j}).  (29)

Thus, by (26) there must exist, independent of j, rational integers C_{0}, C_{1}, C_{2}, …, C_{6} such that if h(x) = C_{0} + C_{1}x + C_{2}x^{2} + ⋯ + C_{6}x^{6}, then

ξ(χ^{j})/q^{4} = J(χ^{j}, χ^{j})^{3}(σ_{5}(J(χ^{j}, χ^{j})))^{2}σ_{3}(J(χ^{j}, χ^{j})) = h(ζ^{j})  (30)

for j such that 7 ∤ j.

6 Some special extended Lucas sequences

We now put λ_{1} = h(ζ^{j}), λ_{3} = h(ζ^{2j}), λ_{5} = h(ζ^{4j}), λ_{2} = h(ζ^{6j}), λ_{4} = h(ζ^{5j}), λ_{6} = h(ζ^{3j}). We observe by (21) and (28) that if we put R = q^{3}, then

λ_{1}λ_{2} = λ_{3}λ_{4} = λ_{5}λ_{6} = R^{2}.

Since λ_{1} = h(ζ^{j}) and λ_{3} = h(ζ^{2j}), we see by (21) and (28) that

q^{8}λ_{1}λ_{3} = ξ(χ^{j})ξ(χ^{2j}) = τ(χ^{j})^{7}τ(χ^{5j})^{7}τ(χ^{2j})^{7}τ(χ^{3j})^{7}
= q^{7}τ(χ^{j})^{7}τ(χ^{3j})^{7} = q^{7}ξ(χ^{3j}) = q^{11}h(ζ^{3j}) = q^{11}λ_{6},

and therefore λ_{1}λ_{3} = Rλ_{6}. Similarly, we find that

λ_{1}λ_{5} = Rλ_{4},  λ_{2}λ_{4} = Rλ_{5},  λ_{2}λ_{6} = Rλ_{3},  λ_{3}λ_{5} = Rλ_{2},  λ_{4}λ_{6} = Rλ_{1}.

Thus, we see that λ_{1}, λ_{2}, λ_{3}, λ_{4}, λ_{5}, λ_{6} satisfy (13) and (14). We also have

μ = λ_{1} + λ_{3} + λ_{5} = 3C_{0} + M_{1}κ + M_{2}κ^{∗}
ν = λ_{2} + λ_{4} + λ_{6} = 3C_{0} + M_{1}κ^{∗} + M_{2}κ,

where

κ = ζ^{j} + ζ^{2j} + ζ^{4j},
κ^{∗} = ζ^{3j} + ζ^{5j} + ζ^{6j},
M_{1} = C_{1} + C_{2} + C_{4}, and
M_{2} = C_{3} + C_{5} + C_{6}.

Since κ+κ^{∗} = −1 and κκ^{∗} = 2, we deduce that T_{1} = μ+ν and T_{2} = μν are rational integers. Thus, by Proposition 7, we find that if we put, S_{1} = T_{1}, S_{2} = RT_{1} + T_{2} − 3R^{2}, and S_{3} is given by (9), the corresponding sequences (U_{n}), (W_{n}) are particular instances of the k = 3 extended Lucas sequences. By [2, Theorem 2.1.4], we find that

J(χ, χ)O = 𝔮_{1}𝔮_{4}𝔮_{5},  J(χ^{5}, χ^{5})O = 𝔮_{4}𝔮_{5}𝔮_{6},  J(χ^{3}, χ^{3})O = 𝔮_{1}𝔮_{3}𝔮_{5};  (31)

however, in this case (p = 7) the cyclotomic field 𝕂 has class number one and is therefore a unique factorization domain; it follows that we can put 𝔮_{j} = π_{j}O (j = 1, 2, …, p − 1), where π_{j} is some prime divisor of q in O. Thus, we can write

J(χ, χ) = π_{1}π_{4}π_{5},  J(χ^{5}, χ^{5}) = π_{4}π_{5}π_{6},  J(χ^{3}, χ^{3}) = π_{1}π_{3}π_{5},

where π_{j} = σ_{j}(π_{1}).

It follows from (29) and (30) that h(ζ) is π_{1}^{4}π_{3}π_{4}^{5}π_{5}^{6}π_{6}^{2}. Suppose that gcd(S_{1}, S_{2}, R) > 1; then q | S_{1} and q | S_{2}. Now since h(ζ) must be one of the six roots of (15), we find that q must divide h(ζ)^{6}, which means that π_{2} must divide h(ζ), an impossibility. Thus, we must have gcd(S_{1}, S_{2}, R) = 1 here. In what follows we will develop some properties of these special extended Lucas sequences that result for the values of S_{1}, S_{2} and R given above.

We first observe that δ = μ − ν = (M_{1} − M_{2})(κ − κ^{∗}); hence, since

(κ − κ^{∗})^{2} = (κ + κ^{∗})^{2} − 4κκ^{∗} = −7,

we get Δ = −7(M_{1} − M_{2})^{2}. Thus, if r is a prime such that r ∤ Δ, then ϵ = (Δ/r) = (−7/r) = (r/7). Suppose r ≡ η (mod 7), where η = ±1; in this case we have ϵ = η and we put m(r) = (r − ϵ)/7. If r ≢ ±1 (mod 7), then we have 7 | r^{2} + ϵr + 1, and in this case we put m(r) = (r^{2} + ϵr + 1)/7.

Now let q be a fixed prime such q ≡ 1 (mod 7) and r be an odd prime such that r ≠ 7, q. Also, let 𝔽_{t} denote the finite field containing t = r^{n} elements, where n = 3(q − 1). Since 𝔽_{t}^{∗} is a cyclic group with generator γ, say, we can put ζ = γ^{(t−1)/7} and ζ_{q} = γ^{(t−1)/q} and repeat the arguments in the previous section concerning the Gauss and Jacobi sums in 𝔽_{t}. We find that all the numbered results in that section hold in 𝔽_{t}. Suppose we let g denote a fixed primitive root of q and put ι = ind_{g} r. Notice that 7 ∤ ι if and only if r^{(q−1)/7} ≢ 1 (mod q).

We will now conduct our calculations in 𝔽_{t}. We observe that by (26) we have

J(χ^{j}, χ^{sj})^{r} = J(χ^{rj}, χ^{rsj}),  (32)

for s such that 7 ∤ s. Also, from the definition of τ(χ^{j}), we get

τ(χ^{j})^{r} = ∑_{i=0}^{q−1} χ^{rj}(i)ζ_{7}^{ri} = ζ^{ιrj}τ(χ^{rj}).  (33)

If m = (r − ϵ)/7, then by (33) and (21) we get

τ(χ^{j})^{7m} = ζ^{ιrj}τ(χ^{j})^{−ϵ}τ(χ^{rj}) = ζ^{ιrj}τ(χ^{j})^{−ϵ}τ(χ^{ϵj}) = ζ^{ιrj}q^{(1−ϵ)/2}.  (34)

It follows that since q^{4m}λ_{1}^{m} = τ(χ^{j})^{7m}τ(χ^{5j})^{7m}, we can conclude from (34) that

λ_{1}^{m} = ζ^{6ιrj}q^{1−ϵ−4m} = ζ^{6ιrj}q^{1−r+3m} = ζ^{6ιrj}R^{m}.  (35)

We also find that

λ_{2}^{m} = ζ^{ιrj}R^{m}, λ_{3}^{m} = ζ^{5ιrj}R^{m}, λ_{4}^{m} = ζ^{2ιrj}R^{m},  (36)
λ_{5}^{m} = ζ^{3ιrj}R^{m}, λ_{6}^{m} = ζ^{4ιrj}R^{m}.

If m = (r^{2} + ϵr + 1)/7, we find by repeated application of (33) that

τ(χ^{j})^{7m} = ζ^{ι(1−r)j}τ(χ^{j})τ(χ^{rj})^{ϵ}τ(χ^{sj}),

where s = r^{2}. Since by (21) we have τ(χ^{rj})^{ϵ} = q^{(ϵ−1)/2}τ(χ^{rϵj}), we get

τ(χ^{j})^{7m} = ζ^{ι(1−r)j}q^{(ϵ−1)/2}τ(χ^{j})τ(χ^{rϵj})τ(χ^{sj}).

Now by (23), we have

τ(χ^{j})τ(χ^{sj}) = J(χ^{j}, χ^{sj})τ(χ^{sj+j}) = J(χ^{j}, χ^{sj})τ(χ^{−ϵrj});

hence, by (21) we find that

τ(χ^{j})^{7m} = ζ^{ι(1−r)j}q^{(ϵ+1)/2}J(χ^{j}, χ^{sj}).

By the reasoning used in the case where m = (r − ϵ)/7, we discover that

λ_{1}^{m} = ζ^{6ι(1−r)j}q^{ϵ+1−4m}J(χ^{j}, χ^{sj})J(χ^{5j}, χ^{5sj}).

We observe that s = r^{2} ≡ 2 or 4 (mod 7). By (25) and (24) we find that in either case, we get

J(χ^{j}, χ^{sj})J(χ^{5j}, χ^{5sj}) = q.

Thus, since ϵ + 2 − 7m = (1 − r)(1 + r + ϵ) we get

λ_{1}^{m} = ζ^{6ι(1−r)j}q^{ϵ+2−4m} = ζ^{6ι(1−r)j}q^{ϵ+2−7m}q^{3m} = ζ^{6ι(1−r)j}R^{m},  (37)

and we also have

λ_{2}^{m} = ζ^{ι(1−r)j}R^{m}, λ_{3}^{m} = ζ^{5ι(1−r)j}R^{m}, λ_{4}^{m} = ζ^{2ι(1−r)j}R^{m},  (38)
λ_{5}^{m} = ζ^{3ι(1−r)j}R^{m}, λ_{6}^{m} = ζ^{4ι(1−r)j}R^{m}.

Thus, in either case when m = m(r), we have μ_{7m} = ν_{7m} = 3R^{7m}. Also, if r ≡ ±1 (mod 7) and 7 ∤ ι , then by (35) and (36) we have μ_{m} = KR^{m} and ν_{m} = K^{∗}R^{m}, where K, K^{∗} ∈ 𝔽_{t}, K + K^{∗} = −1 and KK^{∗} = 2. If r ≢ ±1 (mod 7) and 7 ∤ ι, we also have μ_{m} = KR^{m} and ν_{m} = K^{∗}R^{m}, where K, K^{∗} ∈ 𝔽_{t}, K + K^{∗} = −1 and KK^{∗} = 2. Since (K − K^{∗})^{2} = −7, we must have μ_{m} ≠ ν_{m} for r ≠ 7, whenever 7 ∤ ι. Of course, if 7 | ι, then μ_{m} = ν_{m}.

We are now able to prove the following important result concerning these special extended Lucas sequences.

Theorem 16. Let r be a prime such that r ∤ qΔ and let m = m(r) be defined as above. If the sequences (U_{n}), (W_{n}) are the special extended Lucas sequences defined in this section, then r | D_{7m} and r | U_{m} if and only if r^{(q−1)/7} ≡ 1 (mod q).

Proof. This result follows easily from δU_{n} = μ_{n} − ν_{n}, W_{n} = μ_{n} + ν_{n} and our above remarks.

We are now able to present one of the main results of this paper. This result is the analogue of Theorems 1 and 5 above.

Theorem 17. Let r be a prime such that r ∤ 6qΔ. If 7 ∤ n and r | U_{n}, then r^{(q−1)/7} ≡ 1 (mod q).

Proof. If r | Γ where Γ is given by equation (12), we know by results in [14, §9] that r has a single rank of apparition ψ in (U_{n}) and ψ | r ± 1. Furthermore, it is easy to see from these results that if r | U_{n}, then ψ | n. If r ∤ Γ, by Theorem 9 we know that some rank of apparition ψ of r in (U_{n}) must divide n. Hence, in either case, we have 7 ∤ ψ. Also, if r^{(q−1)/7} ≢ 1 (mod q), then by Theorem 16 we have r ∤ U_{m} and r | U_{7m}, where m = m(r). If r has a single rank of apparition in (U_{n}), then it must be ψ and also a divisor of 7m, but since 7 ∤ ψ, we must have ψ | m, which is impossible because (U_{n}) is a divisibility sequence and r ∤ U_{m}. Thus, if r has more than one rank of apparition in (U_{n}), by Theorem 8 we can only have ψ | r − ϵ, where ϵ = (r/7). If r ≡ ±1 (mod 7), then m = (r − ϵ)/7 and since 7 ∤ ψ and ψ | 7m, we must have ψ | m, which we have already seen is a contradiction. If r ≢ ±1 (mod 7), then m = (r^{2}+ϵr+1)/7. By Theorems 9 and 8, this means that there must be some rank of apparition ϕ of r in (U_{n}) such that ϕ | 7m and ϕ | r − ϵ. Since 7m = (r − ϵ)2 + 3ϵr, this means that ϕ can only be 1 or 3. The former case is impossible because U_{1} = 1. Thus, ϕ must be 3, but since 3 | m, this is also impossible because r ∤ U_{m}.

We next turn to the problem of finding an analogue to Theorems 3 and 4. This is provided by the next results; however, we must first impose some conditions on

N_{n} = A7^{n} + γ_{n}(7) (n > 1),  (39)

the number whose primality we wish to establish. By our results in §4, we may insist that

(i) β_{n}(7) ∤ N_{n} and β_{n}^{∗}(7) ∤ N_{n};

(ii) A ≠ 7^{n} + 2(γ_{n}(7) + 1) + κ_{n}(7) when 2 | A or A ≠ 4 · 7^{n} − 4(γ_{n}(7) + 1) + κ_{n}(7) when 2 ∤ A;

otherwise, N_{n} cannot be a prime.

Let ϵ(N_{n}) be the value of the Legendre symbol (N_{n}/7) = (γ_{n}(7)/7). If γ_{n}(7) ≡ ±1 (mod 7), then γ_{n}(7) ≡ ϵ(N_{n}) (mod 7) and we put m(N_{n}) = (N_{n} − γ_{n}(7))/7. Since N_{n}^{3} ≡ ϵ(N_{n}) (mod 7), we see that 7 | (N_{n}^{2} + ϵ(N_{n})N_{n} + 1) when γ_{n}(7) ≢ ±1 (mod 7), and we put m(N_{n}) = (N_{n}^{2} + ϵ(N_{n})N_{n} + 1)/7. In either case m(N_{n}) is an integer. Furthermore, when γ_{n}(7) ≢ ±1 (mod 7), we must by definition of γ_{n}(7) have N_{n}^{2} + sN_{n} + 1 ≡ γ_{n}(7)^{2} + sγ_{n}(7) + 1 ≡ 0 (mod 7^{n}) for some s ∈ {1, −1}; it follows that s can only be ϵ(N_{n}), and therefore 7^{n} | 7m(N_{n}).

Theorem 18. Let N_{n} be given by (39) such that gcd(N_{n}, 2qΔ) = 1. Suppose further that N_{n} satisfies the conditions (i) and (ii). If A < 2 · 7^{n}, m = m(N_{n}), and N_{n}^{(q−1)/7} ≢ 1 (mod q), then N_{n} is a prime if and only if N_{n} | D_{7m} and N_{n} | U_{7m}/U_{m}.

Proof. We have seen by Theorem 15 that if N_{n} | D_{7m} and N_{n} | U_{7m}/U_{m}, then N_{n} is a prime. Also, by Theorem 16, we see that if N_{n} is a prime, then N_{n} ∤ U_{m}, N_{n} | U_{7m} and N_{n} | W_{7n} − 6R^{7n}. It follows that N_{n} | D_{7m} and N_{n} | U_{7m}/U_{m}.

Theorem 19. Let N_{n} be given by (39) such that gcd(N_{n}, 2qΔ) = 1. Suppose further that N_{n} satisfies the conditions (i) and (ii). If A < 2 · 7^{n}, m = m(N_{n}), and N_{n}^{(q−1)/7} ≢ 1 (mod q), then N_{n} is a prime if and only if

W_{m} ≡ −R^{m}  and  ΔU_{m}^{2} ≡ −7R^{2m} (mod N_{n}).

Proof. Since W_{m} = μ_{m} + ν_{m} and δU_{m} = μ_{m} − ν_{m}, we see by our remarks following (38) that if N_{n} is a prime, then W_{m} ≡ −R^{m} (mod N_{n}) and ΔU_{m}^{2} ≡ −7R^{2m} (mod N_{n}). If W_{m} ≡ −R^{m} (mod N_{n}) and ΔU_{m}^{2} ≡ −7R^{2m} (mod N_{n}), then because

F_{7}(−1/2, −7/4) = 3  and  G_{7}(−1/2, −7/4) = 0,

we must have W_{7m} ≡ 6R^{7m} (mod N_{n}) and N_{n} | U_{7m}/U_{m} by our results at the conclusion of §4 above. It follows from Theorem 18 that N_{n} must be a prime.

7 Computation and an example

We will now discuss how to compute, given q, values for S_{1} and S_{2} for the special extended Lucas sequences introduced in the previous section. Since μ = λ_{1} + λ_{3} + λ_{5} = 3C_{0} + M_{1}κ + M_{2}κ^{∗} and ν = λ_{2} + λ_{4} + λ_{6} = 3C_{0} + M_{1}κ^{∗} + M_{2}κ, where κ + κ^{∗} = −1 and κκ^{∗} = 2, we see that μ + ν = 6C_{0} − M_{1} − M_{2} and μν = 9C_{0}^{2} − 3C_{0}(M_{1} + M_{2}) + 2(M_{1} + M_{2})^{2} − 7M_{1}M_{2}. It follows that

S_{1} = 6C_{0} − M_{1} − M_{2},  (40)
S_{2} = (3C_{0} + R)^{2} − (3C_{0} + R)(M_{1} + M_{2}) + 2(M_{1} + M_{2})^{2} − 7M_{1}M_{2} − 4R^{2}.

Since M_{1} = C_{1} + C_{2} + C_{4} and M_{2} = C_{3} + C_{5} + C_{6}, where

h(ζ^{j}) = C_{0} + C_{1}ζ^{j} + C_{2}ζ^{2j} + ⋯ + C_{6}ζ^{6j}

and by (30)

h(ζ^{j}) = J(χ^{j}, χ^{j})^{3}(σ_{5}(J(χ^{j}, χ^{j})))^{2}σ_{3}(J(χ^{j}, χ^{j})),  (41)

we see that we need to determine B(i, 1) (0 ≤ i ≤ 6), where

J(χ^{j}, χ^{j}) = ∑_{i=0}^{6} B(i, 1)ζ^{ij},

and then use (41) to compute the coefficients C_{i} (i = 0, 1, 2, …, 6).

We have already mentioned one method for computing B(i, 1) (0 ≤ i ≤ 6), but in the case of p = 7 we know by results of Leonard and Williams [9, 10] that there exist integers x_{1}, x_{2}, …, x_{6}, such that

x_{1} ≡ 1 (mod 7),  (42)
72q = 2x_{1}^{2} + 42(x_{2}^{2} + x_{3}^{2} + x_{4}^{2}) + 343(x_{5}^{2} + 3x_{6}^{2}),  (43)
12x_{2}^{2} − 12x_{4}^{2} + 147x_{5}^{2} − 441x_{6}^{2} + 56x_{1}x_{6} + 24x_{2}x_{3} − 24x_{2}x_{4} + 48x_{3}x_{4} + 98x_{5}x_{6} = 0, (44)

12x_{3}^{2} − 12x_{4}^{2} + 49x_{5}^{2} − 147x_{6}^{2} + 28x_{1}x_{5} + 28x_{1}x_{6} + 48x_{2}x_{3} + 24x_{2}x_{4} + 24x_{3}x_{4} + 490x_{5}x_{6} = 0. (45)

Also, if there is a nontrivial (x_{5} and x_{6} not both zero) solution to (42)-(45), we can put B(0, 1) = (q − 2 + x_{1})/7 and B(i, 1) = a_{i} + B(0, 1), where

12a_{1} = −2x_{1} + 6x_{2} + 7x_{5} + 21x_{6},  12a_{2} = −2x_{1} + 6x_{3} + 7x_{5} − 21x_{6},
12a_{3} = −2x_{1} + 6x_{4} − 14x_{5},  12a_{4} = −2x_{1} − 6x_{4} − 14x_{5},
12a_{5} = −2x_{1} − 6x_{3} + 7x_{5} − 21x_{6},  12a_{6} = −2x_{1} − 6x_{2} + 7x_{5} + 21x_{6}.

A table of nontrivial solutions of (42)-(45) for all q ≡ 1 (mod 7) and q < 1000 appears in Williams [22]. For example, if q = 29 this table lists x_{1} = 1, x_{2} = −2, x_{3} = −3, x_{4} = −2, x_{5} = −1, x_{6} = 1 and we find that a_{1} = 0, a_{2} = −4, a_{3} = 0, a_{4} = 2, a_{5} = −1, a_{6} = 2. Thus, in this case, we get

B(0, 1) = 4, B(1, 1) = 4, B(2, 1) = 0, B(3, 1) = 4,
B(4, 1) = 6, B(5, 1) = 3, B(6, 1) = 6.

Williams’s technique for tabulating solutions of (42)-(45) requires that we first have some prime factor λ of q in O. From this is easy to find some associate π_{1} of λ such that J(χ, χ) = π_{1}π_{4}π_{5}, and we can then compute the values of B(i, 1) (0 ≤ i ≤ 6). The main problem here is that of finding some λ (Williams used an old table of Kummer), but since O here is norm-Euclidean, we have an efficient algorithm for computing λ as the greatest common divisor of q and ζ − g^{h}, where h = (q − 1)/7. This is all explained in great detail in the Master’s thesis of Caranay [4].

As mentioned earlier [22, Table 2] provides solutions to the quadratic partition described by equations (42)-(45) for all primes q < 1000 such that q ≡ 1 (mod 7). By use of this table and methods mentioned above we used a computer to calculate the values of S_{1} and S_{2} for each value of q < 1000. The values for S_{1} and S_{2} for each q are given in the table below.

q  S_{1}  S_{2}
29  14965  −1017406826
43  272957  21858615700
71  −1040033  326748793138
113  2975587  731201875780
127  3699863  −97933301720
197 −4964135  −144000965801744
211 −26590621  179982347982148
239 −40502099  526271548075978
281 29450665 −606639016188536
337 −80516773  −201075257844008
379 −107119195 −5558958106936166
421 206278211  10161855131659180
449 213162529  6646761776500900
463 111923783  −13852858246492778
491 95772025 −25034062770947666
547 918783725  281059458133383676
617 −548612555  40672461475028416
631 485050586  4945779937081660
659 −498921389 −313908392056365122
673 89928278 −145075204278786308
701 −386848421 −422179587542810582
743 918668743  100597296170580172
757 −848906535 −647877968552066604
827 −762742499 −1133671841709810608
883 −1331064561 −1555728581709172068
911 1688430505  401503472607970444
953  95807830 −2154081956136898244
967 −2183072893 −504443123489474738

Table 2: Values of S_{1} and S_{2} for each value of q < 1000

We next tabulate S_{3} = RS_{1}^{2} − RS_{2} − 4R^{3}, where R = q^{3} and the factorization of the corresponding Δ, as this is useful in applying the theorems in the previous section.

q  S_{3}  Δ
29  −2939567318323  −7^{7} · 41^{2}
43  437514319995271  −7^{11}
71  −30146872474620481  −7^{7} · 1987^{2}
113  −1350685445842116019  −7^{7} · 1511^{2}
127  −5937522515922653501  −7^{7} · 2689^{2}

197  602743276360621183481  −7^{7} · 83^{2} · 211^{2}
211  −55305165497468656769  −7^{7} · 50147^{2}
239  −2151851544923374759681  −7^{7} · 77237^{2}
281  2471371627931491315493  −7^{11}
337  39263510618353883256277  −7^{7} · 165719^{2}
379  584554850719077350566147  −7^{7} · 174859^{2}
421  −3333118453246404690503  −7^{7} · 13^{6} · 29^{2}
449  −57018536315736139357387  −7^{7} · 71^{2} · 743^{2}
463  82195167713946458240623  −7^{7} · 84211^{2}
491  378058321944546499176803  −7^{7} · 84211^{2}
547 28624865948434380013954111  −7^{3} · 233617^{2}
617 −247393375351235843201779  −7^{7} · 113^{2} · 9941^{2}
631 −6809300717975886628419368  −2^{6} · 7^{7} · 32159^{2}
659 157152662797406306447103779 −7^{7} · 41^{2} · 43^{2} · 139^{2}
673 −22381922654581541570716952 −2^{6} · 7^{7} · 29^{2} · 3067^{2}
701 178907359849478481497829701  −7^{7} · 13^{2} · 29191^{2}
743 −12390466262878082841792637  −7^{7} · 127^{2} · 2297^{2}
757 548179848685234385157559841 −3^{6} · 7^{7} · 29^{2} · 911^{2}
827 887703610865697016843379663  −7^{7} · 251^{2} · 2939^{2}
883 2056619378829343807794316247 −3^{6} · 7^{7} · 113^{2} · 421^{2}
911 −180474348382301748119990917  −7^{7} · 785779^{2}
953 1143201683997473973148592744 −2^{6} · 7^{7} · 71^{2} · 349^{2}
967 2264337669042185334071959087 −7^{7} · 41^{2} · 211^{2} · 421^{2}

Table 3: Values of S_{3} and Δ

The following two tables provide the values of the first 26 terms of (U_{n}) when q = 29 and display how (U_{n}) is analogous to the (G_{n}) given in Table 1. Notice for (U_{n}) the terms with subscripts divisible by 7 tend to have many small factors belonging to no particular residue class, while the other terms satisfy Theorem 17.

n  U_{n}
0  0
1  1
2  63743
3  −178130527
4  −7682842247401
5  866655108578870099
6  −7573915228698089372963
7  −683990034828872027465015352
8  −2397639392414777704627533089857

9  −22408683611098412939809100875710563
10  998749219544949068374614639693399640597
11  86083430660651144394984616218844903262150707
12  −744603639251416281181958726630900817210441654623
13 79150400226551999271197866188077762985564696853513043
14 29653983243922868455568386718402751132322685325618307

67808

15 −56676326670255388502887663794303837738540570772571178

015273923

16 −13610155256109531810220048395596475833684665289317389

49569426882481

17 900974591404181669530727185663463044965078113607329644

8298340027827709

18 −44081029228187672762622309308338538206556842394109679

6845879096253052642797

19 −88341509291730841034147800488133592750487607564356661

92525146740054105545398437

20 366474365369871419422551402809377272895434714580280084

50692950563198615258480194601

21 138353761716273184823923842079896157272158666142471016

8014981086555139364346950488151000

22 3965553744824580859985495851105644891184644442145565571

25010278958585288647718193415730375899

23 5218445524433921420812498124122521433963031486363152233

362945200754150357516907879932060934212437

24 −176249448788214627969811858494667349579382590158574984

2201032900330349269812604886510037926577766168223

25 67573954867428616031053487528800010803524068434362518

8770153722669664064432521414254825560912252408993951 Table 4: U_{n} values for q = 29

n  U_{n}
0  0
1  1
2  63743
3  41^{2} · 105967
4  −63743 · 120528407
5  18080861 · 47932181359
6  −41^{2} · 1217 · 63743 · 105967 · 548099

7  −2^{3} · 3^{3} · 7^{3} · 13 · 83 · 113 · 127 · 181 · 4327 · 22637 · 33629
8  −63743 · 2023951 · 120528407 · 154192040407
9  −41^{2} · 105967 · 352043 · 8608823 · 41508639603521
10  63743 · 199289 · 18080861 · 47932181359 · 90718179089
11  307 · 190553764987279 · 1471511488046122134363179119
12 −41^{2} · 1217 · 1931 · 63743 · 105967 · 528611 · 548099 · 120528407
·799092083
13 911 · 86882985978652029935453201084607862772299337929213
14  2^{6} · 3^{3} · 7^{3} · 13^{3} · 43 · 83 · 113 · 127 · 181 · 461 · 827 · 1093 · 4327

·7043 · 8807 · 22637 · 33629 · 45263 · 63743

15  −41^{2} · 1259 · 4409 · 10499 · 33391 · 105967 · 18080861

·47932181359 · 188657402425248539369

16  −63743 · 2023951 · 3655681 · 120528407 · 154192040407

·270791233327 · 573424602581099359

17  13124329444423469738970728321

·686491904382212805092780937851068123618429

18  −41^{2} · 1217 · 63743 · 105967 · 352043 · 548099 · 8608823

·41508639603521 · 462650775088987947659434651

19  −3191 · 290737 · 19018201 · 500689256569970800812621056

004942512904540952190695696247656811

20  63743 · 199289 · 18080861 · 120528407 · 47932181359

·90718179089 · 304437209057964355560522708661126019

21  2^{3} · 3^{6} · 5^{3} · 7^{3} · 13 · 41^{2} · 43 · 83 · 113 · 127 · 181 · 379 · 4409

·4327 · 11801 · 12263 · 22637 · 33629 · 46831 · 85639 · 105967

·116423 · 887492677 · 780831241
22  307^{3} · 190553764987279 · 1471511488046122134363179119

·63743 · 97789 · 7841244907646133326488341710420059

23  25179078774401811394677769123622574703 · 207253234766

445419497519285309564717099931568281243272800379

24  −41^{2} · 1217 · 1931 · 3191 · 63743 · 105967 · 528611 · 548099

·2023951 · 2425751 · 120528407 · 799092083 · 154192040407

·97986814723666418151903673
25 349^{3} · 2801 · 18080861 · 47932181359 · 617499370923509368494901

·10604913411071362611895961734179080975557912513809901

Table 5: U_{n} values factored for q = 29

Note that in this example each prime divisor r of U_{n} when 7 ∤ n is such that r ≡ ±1, ±17 (mod 58). This is because ±1 and ±17 are the only values of x (mod 29) such that x^{4} = x^{(29−1)/7} ≡ 1 (mod 29).

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] Bruce C. Berndt, Ronald J. Evans, and Kenneth S. Williams, Gauss and Jacobi Sums, John Wiley and Sons, 1998.

[3] David Bressoud and Stan Wagon, A Course in Computational Number Theory, Key College Publishing, 2000.

[4] Perlas Caranay, On Residue Symbols and Kummer’s Reciprocity Law of Degree Seven, Master’s thesis, University of Calgary, 2009.

[5] David A. Cox, Primes of the Form x^{2} + ny^{2}, John Wiley and Sons, 1989.

[6] R. Crandal and C. Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer-Verlag, 2005.

[7] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, 1982.

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

[9] P. A. Leonard and K. S. Williams, A Diophantine system of Dickson, Rend. Accad.Naz. Lincei. 56 (1974), 145–150.

[10] P. A. Leonard and K. S. Williams, The cyclotomic numbers of order seven, Proc. Amer. Math. Soc. 51 (1975), 295–300.

[11] P. Ribenboim, The Book of Prime Number Records, Springer-Verlag, 2 edition, 1989.

[12] E. L. Roettger and H. C. Williams, Public-key cryptography based on a cubic extension of the Lucas functions, Fund. Inform. 114 (2012), 325–344.

[13] E. L. Roettger and H. C. Williams, Some arithmetic properties of certain sequences, J. Integer Sequences 18 (2015), Article 15.6.2.

[14] E. L. Roettger, H. C. Williams, and R. K. Guy, Some extensions of the Lucas functions, in Number Theory and Related Fields: In Memory of Alf van der Poorten, Vol. 43, pp. 271–311, Springer, 2013.

[15] E. L. Roettger, H. C. Williams, and R. K. Guy, Some primality tests that eluded Lucas, Des. Codes Cryptogr. 77 (2015), 515–539.

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

    at https://oeis.org.

[17] Lawrence C. Washington, Introduction to Cyclotomic Fields, Springer-Verlag, 1982.

[18] A. L. Whiteman, Cyclotomy of Jacobsthal sums, Amer. J. Math 74 (1952), 89–99.

[19] H. C. Williams, The primality of N = 2A3^{n} − 1, Can. Math. Bull. 15 (1972), 585–589.

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

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

[22] K. S. Williams, A quadratic partition of primes ≡ 1 (mod 7), Math. Comp 28 (1974), 1133–1136.

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

(Concerned with sequences \underline{A001351}, \underline{A001945}, \underline{A006235} and \underline{A180510}.)

Return to Journal of Integer Sequences home page.