Some Properties of the Lucas Sequence (2,4,14,52,194,...)
The second-order recurrence
s[n] = 4 s[n-1] - s[n-2] (1)
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 sqrt(3), and
in general anything that involves the Pell equation x^2 - 3y^2 = 4.
With the "natural" initial values s[0]=2 and s[1]=4, we have the
sequence
2 4 14 52 194 724 2702 10084 37634 ...
This sequence comprises the integer values of s that satisfy the
Pellian equation
s^2 - 3r^2 = 4 (2)
with the corresponding values of r listed below
s r
----- -----
2 0
4 2
14 8
52 30
194 112
724 418
etc.
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
multiuplication of similar quadratic forms. For example, suppose we
have integers s,r that represent a solution of s^2 - 3r^2 = 4. Then
for any of the infinitely many integer pairs u,v that satisfy the Pell
equation u^2 - 3v^2 = 1 we have
4 = (u^2 - 3v^2)(s^2 - 3r^2) = (us +- 3vr)^2 - 3(ur +- vs)^2
Now, the minimal non-trivial solution of u^2 - 3v^2 = 1 is (2,1),
so beginning with s[0]=2, r[0]=0 we can generate successive solutions
of s^2 - 3r^2 = 4 by the recurrence
s[n] = 2 s[n-1] + 3 r[n-1]
r[n] = 1 s[n-1] + 2 r[n-1]
Naturally the characteristic polynomial for the right hand matrix is
simply the characteristic polynomial
f(x) = x^2 - 4x + 1
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 s[n] - 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
s^2 - 4 = 3r^2
which can be factored to give
(s+2)(s-2) = 3r^2
By construction, s[n] 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
(y+1)(y-1) = 3r^2
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
(y+1)/2 = a^2 (y-1)/2 = 3b^2
which implies that
s[n]-1 = (2a)^2 - 3 = 1 + 3(2b)^2 (n even)
Notice that these are special cases of the quadratic forms
x^2 + Ny^2
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 a^2 - 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 + 3b^2 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 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
(2y+1)(2y-1) = 3(2r)^2
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 s[n]/2 - 1
is not divisible by 3 if n is odd, so we have integers a,b such that
2y + 1 = 3a^2 2y - 1 = b^2
from which it follows that
s[n]-1 = 3(2a^2 - 1) = 2b^2 + 1 (n odd)
So in this case, after factoring out the prime 3, we need only
consider the prime divisors of numbers that have BOTH the forms
x^2 - 2y^2 and x^2 + 2y^2
with x coprime to 2y. It follows that any prime divisor of 2a^2 - 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 2b^2 + 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
s(n)-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 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 s[n]-1 is congruent to 3 (mod 24) for all odd indicies
n, so it's obvious that the product of the remaining factors of
(s[n]-1)/3 must be either 1 or 17. (We can rule out 9 because
2a^2 - 1 cannot be congruent to 9 modulo 24). Therefore, s[n]-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)
1 = 1*1 = 5*5 = 7*7 = 11*11 = 13*13 = 17*17 = 19*19 = 23*23
and
17 = 1*17 = 5*13 = 7*23 = 11*19
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
V(n+2) = 7V(n) + 4 sqrt[V(n)^2 - 12]
This shows that if there exists an index j such that V(j) is
congruent to 1 (mod p) then
V(j+2) = 7 + 12 sqrt(-1) (mod p)
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)
1 = 1*1 = 5*5 = 13*13 = 17*17
and
17 = 1*17 = 5*13
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.
Anyway, Sillke had also stated another conjecture, based on the
observation that a prime p > 3 divides some integer s[n]-1 if and
only if the period of the recurrence of s[j] (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 s[j] modulo primes.
(We'll restrict the discussion to 2nd-order recurrences modulo
primes; for a disucssion of recurrence periods of general nth-order
recurrences modulo primes and composites, see Section 2.7 of
Symmetric Pseudoprimes.
We know the period of s[n] 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 s[n] mod p by T[p], we have
T[p] = (p+1)/k if p = 5 or 7 (mod 12)
(p-1)/k if p = 1 or 11 (mod 12)
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 s[n]-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
p-1 (12j+1)-1 12j
T[p] = --- = --------- = ---
k k k
On the other hand, if p is congruent to 17 (mod 24) then it is of
the form p=12j+5 and we have
p+1 (12j+5)+1 6(j+1)
T[p] = --- = --------- = ------
k k k
This shows that if p divides some s[n]-1 then T[p] 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 s[n]-1, and T[p] cannot be divisible by 6, because in those cases
the numerator of T[p] 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 s[n]-1:
p T[p] k
-- ---- ---
13 12 1
17 18 1
37 36 1
41 * 14 3
61 60 1
73 36 2
89 90 1
97 * 16 6
109 108 1
113 114 1
137 138 1
157 156 1
181 * 20 9
193 24 8
229 228 1
233 234 1
241 30 8
257 258 1
277 * 92 3
281 282 1
313 78 4
337 * 56 6
349 * 116 3
353 * 118 3
373 * 124 3
397 396 1
401 402 1
409 204 2
421 420 1
433 216 2
449 150 3
457 228 2
521 * 58 9
541 540 1
569 114 5
577 288 2
593 594 1
601 300 2
613 204 3
617 618 1
641 642 1
661 60 11
673 336 2
709 708 1
733 * 244 3
757 84 9
761 762 1
769 192 4
809 810 1
829 276 3
853 * 284 3
857 858 1
877 876 1
881 294 3
929 930 1
937 234 4
953 954 1
977 * 326 3
997 996 1
As required, gcd(k,6) > 1 for all cases where T[p] 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
T[p] 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.
Anyway, we're now in a position to prove Sillke's second conjecture,
i.e., the observation that the period of the recurrence
s[0] = 2
s[1] = 4
s[n] = 4 s[n-1] - s[n-2]
modulo p is divisible by 6 if any only if p divides s[n]-1 for some
integer n. The key identity is
s[n+k] + s[n-k] = s[n] s[k] (1)
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
s[n]-1 for some particular index n. In other words, we have s[n]=1
(mod p). It follows from (1) if we set k=n we have
s[2n] = s[n]^2 - 2 (2)
= (1)^2 - 2 (mod p)
= -1 (mod p)
(Of course, it also follows that s[4n], s[8n], etc., are all congruent
to -1 (mod p).) We also know that s[k]=s[-k] for all k, so on the
condition that there is an integer n such that s[n]=1 (mod p) we have
s[-2n] = -1
s[ -n] = 1
s[ 0] = 2 (mod p)
s[ n] = 1
s[ 2n] = -1
This provides more than enough values to infer the recurrence relation
for the sequence in steps of n:
s[n(k)] = s[n(k-1)] - s[n(k-2)] (mod p) (3)
so we have the complete cycle
s[ 0] = 2
s[ n] = 1
s[2n] = -1 (mod p)
s[3n] = -2
s[4n] = -1
s[5n] = 1
s[6n] = 2
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 s[n]-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 s[n]=1 (mod p) for
some index n? Yes, because if the period of the recurrence is 6m
we know that s[6m]=2 (mod p), which by equation (2) implies that
s[3m] = +2 or -2 (mod p). We also have the relation
2 s[3m] = 3 s[m] s[2m] - s[m]^3
which implies that
+2 or -1 if s[3m] = +2
s[m] =
-2 or +1 if s[3m] = -2
Now, it's important to realize that we can rule out any value of the
sequence being congruent to +2 (mod p) between s[0] and s[6m], because
the sequence has a fundamental period j if and only if j is the least
positive integer such that s[j]=2. This is due to the fact that the
meta-sequence s[-j], s[0], s[j], s[2j],... has a period of 1, and
therefore every sequence s[kj + 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 s[kn] is
s[kn] = s[k] s[k(n-1)] - s[k(n-2)]
and so if s[k]=2 (mod p) for any index k we have
s[kn] = 2 s[k(n-1)] - s[k(n-2)]
which has the characteristic polynomial
x^2 - 2x + 1 = (x-1)^2
In other words, it factors into the degenerate 1st-order recurrence
s[kn] = s[k(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
s[km+r] = s[k(m-1)+r]
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 s[3m] = -2, which implies that
s[m] = +1 or -2. However, if s[m]=-2 then s[2m]=+2, which is
impossible, so we must have s[m]=1 (mod p), which proves that p
divides s[m]-1. This concludes the proof of Sillke's 2nd conjecture.
By the way, it's interesting to observe that if p divides some s[n]-1
then we have the meta sequence of values
+2 *----------------------------------*--
+1 -----*-----------------------*-------
0 -------------------------------------
-1 -----------*-----------*-------------
-2 -----------------*-------------------
Moreover, recall from my previous email that most of the periods are
actually divisible by 12, and some by 24, and in those cases we know
that p divides s[u] itself, which means that s[u]=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
+2 *-----------------------------------*--
+1 -----*-----------------------*--------
0 --------*-----------------*----------
-1 -----------*-----------*-------------
-2 -----------------*-------------------
These are precisely the lattice values of 2cos(2pi k/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 S[k]=s[nk] given by equation (3)
has the characteristic equation x^2 - x + 1, whose roots are the
primitive cube roots of -1, i.e.,
r1 = (1+sqrt(-3))/2 r2 = (1-sqrt(-3))/2
and of course the values of the recurrence are simply
S[k] = (r1)^k + (r2)^k
If we write r1 and r2 in exponential form we have
r1 = e^(ia) r2 = e^(-ia)
Recall that the definition of the cosine function is
e^(iq) - e^(-iq)
cos(q) = ------------------
2
so we have S[k] = 2 cos(k pi/6).
Return to MathPages Main Menu
Сайт управляется системой
uCoz