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]