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).