3.0 Congruence Conditions On The Terms Of Linear Recurring Sequences 

3.1 Second Order Recurrences 

To determine congruence conditions on the terms of a linear recurring sequence, we must first determine a closedform expression for the nth term using only rational functions and root extractions. Consider the second order recurrence 

_{} 

This recurrence corresponds to a first order recurrence of the form 

_{} 

where a, b, and D are constants. Let r_{n} denote the sum of the roots of the characteristic polynomial of (2). The initial value is r_{0} = 1, and all subsequent values can be generated recursively using (2). Now we define a_{n} and b_{n} by the formal relation 

_{} 

from which we get 
_{} 

The sequences a_{n} and b_{n} each individually satisfy the second order recurrence (1), provided we take the coefficients 

_{} 

Setting D equal to the determinant, this implies a = c_{1}/2 and b = 1/2, so we have 

_{} 

By construction the a_{n} and b_{n} sequences are integers (assuming c_{1} and c_{2} are integers) with the initial values 

_{} 

For any prime p we have 

_{} 

Therefore 
_{} 

modulo p, where [D/p] denotes the Legendre symbol. Since the sequences A_{n} and B_{n} are linearly independent, we can now express congruence conditions on the pth element of any integer sequence that satisfies the general homogeneous recurrence relation (1). For example, the basis sequence elements satisfy the congruences 

_{} 

We can also determine quadratic congruence conditions on the elements b_{0}(m) and b_{1}(m) where m = (p1)/2. 


3.2 Third Order Recurrences 

In the quadratic case we found that the roots of the general quadratic polynomial were given by the closed form of the linear recurrence term. In this section we show that the solution of the general cubic is given by the closed form of the third order linear recurrence. 

A set of three linearly independent solutions of the recurrence 
_{} 
can be found by considering a first order recurrence of the form 
_{} 
where a,b,g,D are real (but D^{1/3} and D^{2/3} are complex). Letting r(n) denote the nth power of the characteristic root of (4), we have the following initial values 



where 
_{} 

Since the three components of each value are incomensurate, these components are each solutions of the same recurrence as the characteristic recurrence of r(n). Identifying this with the general third order recurrence (3), we have three equations in the three unknown coefficients c_{1},c_{2},c_{3}. Solving these equations gives 
_{} 

Therefore, we immediately have 
_{} 
Substituting this into the equations for b and g leads us to define quantities u and v as follows 
_{} 
and 
_{} 
Eliminating either b or g from these equations leads to a quadratic equation with the roots 

_{} 
Therefore, we have 
_{} 
By its construction, this is the general form of the roots of the characteristic polynomial of (1), i.e., the general cubic 
_{} 


3.3 Fourth Order Recurrences 

Given any integer k and a sequence of integers s_{0}, s_{1}, s_{2},... that satisfies a fourth order linear homogeneous recurrence relation for which the resolvant cubic of the characteristic quartic has a rational root, this section describes a method for determining the primes p such that s_{p }º k (mod p). 

Consider the general homogeneous fourth order recurrence 
_{} 
To analyze this recurrence we first consider the following second order recurrence with complex coefficients 
_{} 
where a, b, c, and d are real. Let r(n) denote the sum of the nth powers of the roots of the characteristic polynomial of (6). The initial values are 
_{} 
and all subsequent r(n) can be generated using (6). If we let A_{n} and B_{n} denote, respectively, the real and imaginary coefficients of r(n), then we have 
_{} 
Seperating the real and imaginary components, we find that the sequences A_{n} and B_{n} each individually satisfy the fourth order recurrence (5) with the coefficients 
_{} 
These equations imply that a = k_{1}/2 and c = y/2 where y is a root of the cubic 

_{} 
with 
_{} 
Equation (7) is called the resolvant cubic of the quartic polynomial corresponding to (5). If x_{1}, x_{2}, x_{3}, x_{4} are the roots of the characteristic equation of (5), and y_{1}, y_{2}, y_{3} are the roots of (7) then 

_{} 

Given the value of c based on any root y of (7), the corresponding values of b and d are 

_{} 

_{} 
with the stipulation that 
_{} 

This last condition relates the signs of b and d, and is a useful identity for ring multiplication to be discussed later. 

Example: 
To illustrate, consider the fourth order recurrence 
_{} 
whose characteristic polynomial 
_{} 

is irreducible (according to Eisenstein's criterion). For this case we have 

k_{1} = ‑2_{}k_{2} = 0_{}k_{3} = 4_{}k_{4} = 2 

which gives a = ‑1 and 
_{} 

Taking the root c = ‑1, we can use (8) and (9) to compute b = ±1 and d = ±1. Now, since (10) gives bd = 1, it follows that b and d have the same sign. Choosing b = d = ‑1, equation (6) gives the second order complexvalued recurrence 

_{} 
with the characteristic equation 
_{} 
If we let r(n) = A_{n }+ iB_{n} denote the sum of the nth powers of the complex roots of h(z), then we have the initial values 

By their construction, both of these sequences individually satisfy the original fourth order realvalued recurrence (11) for n > 4. If s(n) denotes the sum of the nth powers of the roots of (12), then s(n) = 2A_{n}. 

Now, if p is an odd prime, we have the following congruences 
_{} 
from which it follows that 
_{} 
To complete the analysis of the general fourth order recurrence we need two more solutions C_{n} and D_{n} which, together with A_{n} and B_{n}, will form a basis for all possible solutions. That is, any solution X_{n} of (11) will be expressible as 
_{} 
where the g_{m} are constants determined by the initial values of X_{n}. Any four solution sequences constitute a basis provided that they are linearly independent, for which a necessary and sufficient condition is that the determinant 
_{} 
is nonzero. However, our purpose is to define primality criteria for every possible X_{p}, which requires that we be able to define congruence conditions on C_{n} and D_{n} when n is a prime, similar to the conditions on A_{n} and B_{n} given by equations (15). Our approach will be to derive another second order complexvalued recurring sequence, different from (14), but with real and imaginary parts that also satisfy the basic fourthorder recurrence (11). 

One possibility would be to use a = c = ‑1 as before, but choose the signs b = d = +1. However, this does not lead to independent sequences. Instead, we keep a = ‑1 and return to the cubic (13) for a different value of c. Factoring out the root c = ‑1 leaves 
_{} 
which has the roots _{}. To make b and d real valued we choose the root c = _{}, which results in the following set of coefficients 
_{} 

It is useful to observe that, in view of (10), we have 
_{} 
Inserting these values of a, b, c, and d into equation (6) gives a second order complexvalued recurrence with the characteristic polynomial 
_{} 
Again letting r(n) denote the sum of the nth powers of the roots of h(z), we have the initial values 
_{} 
By their construction, the real and the imaginary parts of r(n), taken seperately, both satisfy the basic fourth order recurrence (11). Clearly the real part of this r(n) is identical to the A_{n} sequence already discussed. Our objective is to derive two new and independent integer sequences from the imaginary part of this r(n). Letting I(n) denote the coefficient of the imaginary part of r(n), we have the initial values 
_{} 
As a consequence of equation (10), the irrational quantities b and d are related by 
_{} 
so every element of the I(n) sequence can be expressed in the form 
_{} 
where a_{n} and b_{n} are rational coefficients. The values of I(0) and I(1) are already of this form. The remaining initial values are 
_{} 
In order to deal only with integer sequences, we will work with 3I(n) instead of I(n), and we will define the two new basis sequences C_{n} and D_{n} as follows 

_{} 

The initial values of these sequences are 



The four sequences A_{n}, B_{n}, C_{n}, and D_{n} are linearly independent, as shown by the nonzero determinant 
_{} 
It remains to establish congruence requirements on C_{p} and D_{p} for primes p. We know that 
_{} 
For the remainder of this section, all congruences are understood to be modulo p. Concerning ourselves only with the imaginary part, we have 
_{} 
Therefore, by equation (17) we have 
_{} 
and also 
_{} 
from which it follows that 
_{} 

where [‑1/p] is the Legendre symbol. Furthermore, squaring congruences (18) and (19), and multiplying by (2_{}), we have 
_{} 

_{} 
Expanding the right side using the binomial theorem, we have 
_{} 
and 
_{} 
Dividing (21) by 2, and (22) by ‑1, and noting that 2^{p‑1}º1 and 13^{(p‑1)/2} º [13/p] (Euler's criterion), we have 
_{} 
and 
_{} 
Subtracting (23) from (24) and dividing by 9 gives 

_{} 
Substituting this into (23) gives 
_{} 
Recalling equation (20) 
_{} 

we can solve (25) and (20) simultaneously for C_{p}^{2} and 13D_{p}^{2}, which gives 

_{} 

_{} 
Letting F and q denote, respectively, the right sides of equations (26) and (27), we have the following complete set of basis element congruences for any prime p: 
_{} 

along with the condition 
_{} 
In view of equation (16), the residue class of X_{p} for any sequence of integers X that satisfies the basic recurrence (11) is given by 
_{} 
where the g_{i} may be expressed in terms of the initial values of the X sequence by solving the simultaneous equations 
_{} 
Since the determinant of the basis matrix is 12, and we want to deal only with integers, we multiply (29) by 12 to clear any fractional values of the g_{i}, and then define G_{i} = 12g_{i} . Also, to clear the radicals from (29) we can bring the first two terms on the right over to the left, and then square both sides (bearing in mind that the crossproduct of radicals is an integer by equation (28)) to give a quadratic congruence condition on X_{p}. Since the square of the term Ö(q/13) has a 13 in the denominator, we will multiply through by 13 to give the general form 
_{} 
Notice that if the prime p is not equal to 13, we can divide this congruence by 13 whenever q (mod p) is divisible by 13, which it is when [‑1\p] = +1. Also, if p is not equal to 2 or 3, we may be able to divide by these factors. 

To illustrate, consider the particular solution sequence X of recurrence (11) with the initial values X_{0} = 37, X_{1} = 19, X_{2} = 43, and X_{3} = 101. The values of g_{i} and G_{i} for this sequence are 

g_{1} = 37/2_{}G_{1} = 222 
g_{2} = ‑121/2 _{}G_{2} = ‑726 
g_{3} = ‑61/3_{}G_{3} = ‑244 
g_{4} = ‑439/3_{}G_{4} = ‑1756 

Therefore, for any prime p other than 2, 3, or 13, we have the following quadratic congruences on X_{p}: 
_{} 
These congruences enable us to easily determine the primes p such that X_{p} º y (mod p) for any integer y. For example, the only primes p that divide X_{p} are 109, 547, and 195691. Also, the only primes p such that X_{p} º 5000 (mod p) are 3 and 157560691. 
