Some Properties of the Lucas Sequence

 

The second-order recurrence

 

 

arises in many different situations, such as in the sequence of "Lucas Numbers" used in primality tests of Mersenne numbers, and in Heronian triangles, and continued fractions for , and in general anything that involves the Pell equation x2 - 3y2 = 4. With the "natural" initial values s0 = 2 and s1 = 4, we have the sequence

 

 

This sequence comprises the integer values of s that satisfy the Pellian equation

 

 

with the corresponding values of r listed below

 

 

I referred to (2) as "Pellian" rather than a Pell equation proper, because the right hand side is not unity. However, given any solution of the Pellian equation we can obviously construct others by simple multiplication of similar quadratic forms. For example, suppose we have integers s,r that represent a solution of s2 - 3r2 = 4. Then for any of the infinitely many integer pairs u,v that satisfy the Pell equation u2 - 3v2 = 1 we have

 

 

Now, the minimal non-trivial solution of u2 - 3v2 = 1 is (2,1), so beginning with s0 = 2, r0 = 0 we can generate successive solutions of s2 - 3r2 = 4 by the recurrence

 

 

Naturally the characteristic polynomial for the right hand matrix is simply the characteristic polynomial

 

 

of the 2nd-order recurrence (1), and that recurrence itself can be recovered by eliminating r from the two first-order equations.

 

Torsten Sillke noticed, based on numerical evidence, that if p > 3 is a prime divisor of sn - 1 then apparently p is necessarily congruent to 1 or 17 (mod 24) if n is odd, and it is congruent to 1 or 13 (mod 24) if n is even. He asked if this is true in general and, if so, for a proof.

 

To prove that this conjecture is correct, let's re-write the basic Pellian equation in the form

 

 

which can be factored to give

 

 

By construction, sn is divisible by exactly one power of 2 if n is even, and by two powers of 2 if n is odd. Now, if n is even, there is an odd integer y such that y = s/2, and we have

 

 

where the two factors on the left are coprime except for a single common factor of 2. Also, from congruence considerations we know that s/2 + 1 is not divisible by 3, so we have integers a,b such that

 

 

which implies that

 

 

Notice that these are special cases of the quadratic forms

 

 

where gcd(x,Ny) = 1. Euler (and probably Fermat) proved that, for the cases N = 1, 2, 3, every prime divisor of this form is also expressible in this form, and the prime p can divide a number of this form if and only if (-N) is a square modulo p. Thus, any prime divisor of a number of the form a2 - 3 (with a prime to 3) must be congruent to 1, 11, 13, or 23 modulo 24, because those are the only primes modulo which 3 is a square. Likewise, any prime divisor of a number of the form 1 + 3b2 must be congruent to 1, 7, 13, or 19 modulo 24, because those are the prime modulo which -3 is a square. Now, since s(n) - 1 must be of both those forms if n is even, it's clear that any prime divisor must be in the intersection of those two sets of residues, so it can only be 1 or 13 (mod 24).

 

For the case of odd n there is an odd integer y such that 2y = s/2, and we have

 

 

The two factors on the left are coprime, so one must be a square and the other must be 3 times a square. It's easy to show that sn/2 - 1 is not divisible by 3 if n is odd, so we have integers a,b such that

 

 

from which it follows that

 

 

So in this case, after factoring out the prime 3, we need only consider the prime divisors of numbers that have both the forms

 

 

with x coprime to 2y. It follows that any prime divisor of 2a2 - 1 must be a prime p modulo which 2 is a square, so p must be congruent to 1, 7, 17, or 23 (mod 24). Also, any prime divisor of 2b2 + 1 (other than 3) must be a prime p modulo which -2 is a square, so p must be congruent to 1, 3, 11, 17, or 19 (mod 24). Again, since sn - 1 must be of both those forms if n is odd, it's clear that any prime divisor must be in the intersection of those two sets of residues, so it can only be 1 or 17 (mod 24) (once we have factored out the power of 3). This completes the proof of Sillke's conjecture.

 

Incidentally, without even invoking the theory of quadratic forms we can nearly prove the above result by simple congruence considerations. We know that sn - 1 is congruent to 3 (mod 24) for all odd indices n, so it's obvious that the product of the remaining factors of (sn - 1)/3 must be either 1 or 17. (We can rule out 9 because 2a2 - 1 cannot be congruent to 9 modulo 24). Therefore, sn - 1 = 3m where m = 1 or 17. If m is a prime, then we are done. If m is composite, the question is whether each of the prime factors of m is necessarily congruent to 1 or 17 (mod 24).

 

If we examine the multiplication table (mod 24) we find that if m = uv then the only possible values of the factors u and v are (mod 24)

 

 

and

 

Therefore, any prime factors of m must be in one of these residue classes. However, we can exclude many of these, recalling the fact that

 

 

This shows that if there exists an index j such that V(j) is congruent to 1 (mod p) then

 

 

which implies that -1 must be a square modulo p, which means that p = 1 (mod 4). Thus we can rule out p = 7, 11, 19, or 23 (mod 24), which just leaves the following possibilities for any 2-part factorizations of m (mod 24)

 

 

and

 

So, the only part of Sillke's conjecture (for odd n) that requires the theory of quadratic forms is the assertion that 5 and 13 are ruled out.

 

Sillke had also stated another conjecture, based on the observation that a prime p > 3 divides some integer sn - 1 if and only if the period of the recurrence of sj (mod p) is a multiple of 6. This conjecture is not too difficult to prove. First, let's review a little what's known about the periods of sj modulo primes. (We'll restrict the discussion to 2nd-order recurrences modulo primes; for a discussion of recurrence periods of general nth-order recurrences modulo primes and composites, see Section 2.7 of Symmetric Pseudoprimes.

 

We know the period of sn mod p divides p+1 if 3 is not a quadratic residue mod p, and divides p - 1 otherwise. Thus, if we denote the period of sn mod p by Tp, we have

 

 

Of course, the primes congruent to 5 or 7 (mod 12) are congruent to 5,7,17, or 19 (mod 24), and the primes congruent to 1 or 11 (mod 12) are congruent to 1,11,13, or 23 (mod 24).

 

Now, remember that the only primes that divide sn - 1 are congruent to 1, 13, or 17 (mod 24). If p is congruent to 1 or 13 then it is of the form p = 12j + 1, and so

 

 

On the other hand, if p is congruent to 17 (mod 24) then it is of the form p = 12j + 5 and we have

 

 

This shows that if p divides some sn - 1 then Tp must be a multiple of 6 if k = 1, i.e., if the recurrence corresponds to a primitive root (mod p).

 

Conversely if p is congruent to 7 or 11 (mod 12), it cannot divide any sn - 1, and Tp cannot be divisible by 6, because in those cases the numerator of Tp is either 12j + 8 or 12j + 10, neither of which is divisible by 6 for any value of k.

 

In view of all this, it's clear why Sillke's conjecture is likely to apply to most primes. The only uncertainty is whether k might divide out the 6 from the numerator of some period. This is essentially the same phenomenon that allows pseudoprimes to occur, i.e., aliasing, so that a field with one characteristic "looks like" a field with another, because k > 1.

 

To illustrate, here's a list of the primes that are in the "right" congruence classes to be possible divisors of s[n]-1, along with their periods and the corresponding values of k. I'll put an asterisk (*) next to those that do not divide sn - 1:

 

 

p T[p] k p T[p] k

-- ---- --- --- --- ---

13 12 1 449 150 3

17 18 1 457 228 2

37 36 1 521 * 58 9

41 * 14 3 541 540 1

61 60 1 569 114 5

73 36 2 577 288 2

89 90 1 593 594 1

97 * 16 6 601 300 2

109 108 1 613 204 3

113 114 1 617 618 1

137 138 1 641 642 1

157 156 1 661 60 11

181 * 20 9 673 336 2

193 24 8 709 708 1

229 228 1 733 * 244 3

233 234 1 757 84 9

241 30 8 761 762 1

257 258 1 769 192 4

277 * 92 3 809 810 1

281 282 1 829 276 3

313 78 4 853 * 284 3

337 * 56 6 857 858 1

349 * 116 3 877 876 1

353 * 118 3 881 294 3

373 * 124 3 929 930 1

397 396 1 937 234 4

401 402 1 953 954 1

409 204 2 977 * 326 3

421 420 1 997 996 1

433 216 2

 

As required, gcd(k,6) > 1 for all cases where Tp is not divisible by 6. In fact, all the non-divisors have k a multiple of 3. This might lead us to suspect the converse, i.e., that p cannot be a divisor if k is a multiple of 3, but that's is certainly not the case, as shown by the primes 449, 613, 757, 829, etc. On the other hand, we might suspect that p must be a divisor if k is not divisible by 3, and this is certainly true for all p < 1000. This really just expresses the fact that all the periods are even numbers, so divisibility by 3 automatically implies divisibility by 6.

 

By the way, notice that in most (2/3) of the cases, the numerator of Tp is automatically not only a multiple of 6, it is a multiple of 12, so it has a power of 2 to spare. Also, in 1/3 of the cases the numerator is a multiple of 24, so it has two powers of 2 to spare.

 

We're now in a position to prove Sillke's second conjecture, i.e., the observation that the period of the recurrence

 

 

modulo p is divisible by 6 if any only if p divides sn - 1 for some integer n. The key identity is

 

 

for any integers n and k. (Notice that with n = 1 this is simply a re-statement of the basic recurrence, and it's easy to show by induction that it's true for all n.) Now, suppose a prime p divides sn - 1 for some particular index n. In other words, we have sn = 1 (mod p). It follows from (3) if we set k = n we have

 

 

(Of course, it also follows that s[4n], s[8n], etc., are all congruent to -1 (mod p).) We also know that sk = s-k for all k, so on the condition that there is an integer n such that sn = 1 (mod p) we have

 

 

This provides more than enough values to infer the recurrence relation for the sequence in steps of n:

 

 

so we have the complete cycle

 

 

which repeats ad infinitum. The period of the recurrence (mod p) must be a multiple of this cycle, so it must be divisible by 6. So we've proven that if p divides some sn - 1 then the period of the recurrence (mod p) must be divisible by 6.

 

What about the converse? If the period of the recurrence is a multiple of 6, must we necessarily find that sn = 1 (mod p) for some index n? Yes, because if the period of the recurrence is 6m we know that s6m = 2 (mod p), which by equation (4) implies that s3m = +2 or -2 (mod p). We also have the relation

 

 

which implies that

 

 

Now, it's important to realize that we can rule out any value of the sequence being congruent to +2 (mod p) between s0 and s6m, because the sequence has a fundamental period j if and only if j is the least positive integer such that sj = 2. This is due to the fact that the meta-sequence s-j, s0, sj, s2j,... has a period of 1, and therefore every sequence skj+r has period 1. (A full account of this is given in Section 2.5 of Symmetric Pseudoprimes. The key point is that the recurrence for the sequence skn is

 

 

and so if sk = 2 (mod p) for any index k we have

 

 

which has the characteristic polynomial

 

 

In other words, it factors into the degenerate 1st-order recurrence skn = sk(n-1), and since n can be any rational number such that kn is an integer, we can set n = m + r/k to give

 

 

which shows that the entire s sequence has period k.

 

Therefore, since the premise is that 6m is the fundamental period of the recurrence (mod p), we know that s3m = -2, which implies that sm = +1 or -2. However, if sm = -2 then s2m = +2, which is impossible, so we must have sm = 1 (mod p), which proves that p divides sm - 1. This concludes the proof of Sillke's 2nd conjecture.

 

By the way, it's interesting to observe that if p divides some sn - 1 then we have the meta sequence of values

 

 

Moreover, recall that most of the periods are actually divisible by 12, and some by 24, and in those cases we know that p divides su itself, which means that su = 0 (mod p) for some u. Indeed, we find that the 0's always occur mid-way between the +1 and -1, so we have

 

 

These are precisely the lattice values of 2cos(2pk/T) where T is the period of the recurrence modulo p. This function will give a value of 1 if and only if there is an integer k such that k/T = 1/6, which there will be iff the period T is a multiple of 6.

 

It isn't surprising that we have this relation, because notice that the recurrence of the meta-sequence Sk = snk given by equation (5) has the characteristic equation x2 - x + 1, whose roots are the primitive cube roots of -1, i.e.,

 

 

and of course the values of the recurrence are simply

 

 

If we write r1 and r2 in exponential form we have

 

 

Recalling that the definition of the cosine function is cos(q) = (eiq + e-iq)/2, we have the result Sk = 2 cos(kp/6).

 

Return to MathPages Main Menu