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 closed-form expression for the nth term using only rational functions and root extractions. Consider the second order recurrence
This recurrence can be reduced to the following first order recurrence with complex coefficients
where a,b are real. 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). If we let An and Bn denote, respectively, the coefficients of the real and imaginary parts of r(n), then (2) gives
Separating the real and imaginary components, we find that the sequences An and Bn each individually satisfy the second order recurrence (1) where the coefficients c1 and c2 are given by
It follows that
and therefore
where D equals the discriminant c12 - 4c2. We now define the two sequences a (n) and b (n) as follows
Clearly, each of these sequences is integer-valued and satisfies the second order recurrence (1). We have
The initial values of the a and b sequences are
For any prime p we have
Therefore
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). In particular, the basis sequence elements satisfy the congruences
We can also determine congruence conditions on the elements b0(m) and b1(m), where m = (p-1)/2, as follows
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 D1/3 and D2/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 c1,c2,c3. 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 s0, s1, s2,... 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 sp 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 An and Bn denote, respectively, the real and imaginary coefficients of r(n), then we have
Seperating the real and imaginary components, we find that the sequences An and Bn each individually satisfy the fourth order recurrence (5) with the coefficients
These equations imply that a = k1/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 x1, x2, x3, x4 are the roots of the characteristic equation of (5), and y1, y2, y3 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
k1 = -2
k2 = 0k3 = 4k4 = 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 complex-valued recurrence
with the characteristic equation
If we let r(n) = An + iBn 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 real-valued recurrence (11) for n > 4. If s(n) denotes the sum of the nth powers of the roots of (12), then s(n) = 2An.
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 Cn and Dn which, together with An and Bn, will form a basis for all possible solutions. That is, any solution Xn of (11) will be expressible as
where the gm are constants determined by the initial values of Xn. 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 non-zero. However, our purpose is to define primality criteria for every possible Xp, which requires that we be able to define congruence conditions on Cn and Dn when n is a prime, similar to the conditions on An and Bn given by equations (15). Our approach will be to derive another second order complex-valued recurring sequence, different from (14), but with real and imaginary parts that also satisfy the basic fourth-order 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 complex-valued 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 An 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 bn 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 Cn and Dn as follows
The initial values of these sequences are
The four sequences An, Bn, Cn, and Dn are linearly independent, as shown by the non-zero determinant
It remains to establish congruence requirements on Cp and Dp 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 2p-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 Cp2 and 13Dp2, 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 Xp for any sequence of integers X that satisfies the basic recurrence (11) is given by
where the gi 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 gi, and then define Gi = 12gi . 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 cross-product of radicals is an integer by equation (28)) to give a quadratic congruence condition on Xp. 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 X0 = 37, X1 = 19, X2 = 43, and X3 = 101. The values of gi and Gi for this sequence are
g1 = 37/2G1 = 222
g2 = -121/2 G2 = -726
g3 = -61/3G3 = -244
g4 = -439/3G4 = -1756
Therefore, for any prime p other than 2, 3, or 13, we have the following quadratic congruences on Xp:
These congruences enable us to easily determine the primes p such that Xp y (mod p) for any integer y. For example, the only primes p that divide Xp are 109, 547, and 195691. Also, the only primes p such that Xp 5000 (mod p) are 3 and 157560691.