From: Kevin Brown [SMTP:ksbrown@seanet.com]
To: 'TORSTEN.SILLKE@LHSYSTEMS.COM'
Subject: RE: lucas sequences
Sent: 6/25/98 4:09 AM
Hello,
It occurred to me how to prove your conjecture #2, 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 (mod p) (2)
= (1)^2 - 2
= -1
(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. (See
section 2.5 of my symmetric pseudoprimes paper for a proof
of this.)
Therefore, 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 your Conjecture #2.
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).
Regards,
Kevin
Reference:
Kevin Brown;
"Symmetric Pseudoprimes"
http://www.seanet.com/~ksbrown/
(1) is the Q=1 case of the addition relation
for general Lucas sequences.
V[n] = a^n + b^n, Q=ab
V[m+n] + Q^n V[m-n] = V[m] V[n]