From - Tue Jun 30 09:38:01 1998 From: Robin Chapman Newsgroups: sci.math Subject: Re: Some Properties of the Lucas Sequence (2,4,14,52,194,..) Date: Mon, 29 Jun 1998 08:51:57 GMT Organization: University of Exeter Lines: 91 Message-ID: <6n7kjd$bfm$1@nnrp1.dejanews.com> References: <3595a681.42854989@news.seanet.com> In article <3595a681.42854989@news.seanet.com>, ksbrown@seanet.com wrote: > > 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 with consecutive integer edges, and continued > fractions for sqrt(3), and so on. 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 ... > Based on numerical evidence, Torsten Sillke noticed 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. Here's an alternative approach. Let alpha = 2 + sqrt(3). Then s[n] = alpha^n + alpha ^{-n}. For p = 1 or 11 (mod 12) 3 is a square in F_p and so let's pick a square root of sqrt(3) in F_p and consider alpha as an element of F_p. If p = 5 or 7 (mod 12) then 3 isn't a square in F_p so consider alpha as an element of F_{p^2}. Let k = F_p or F_{p^2} as appropriate. Suppose p > 3 and p | s[n] - 1. Then p | alpha^n - 1 + alpha^(-n) = (alpha^(3n) + 1)/alpha^n(alpha^n + 1). Thus p | alpha^(3n) in Z[sqrt(3)] but p does not divide alpha^n + 1, since if it did, it would also divide alpha ^(2n) - alpha^n + 1 - (alpha^n + 1)(alpha - 2) = 3. In k then, alpha^(3n) = -1 but alpha^n <> -1, and so alpha^n has order 6 in k^*. But for p = 1 or 11 (mod 12), alpha^(p-1) = 1 and so p-1 is divisible by 6 and p = 1 (mod 12). For p = 5 or 7 mod 12, then alpha^p = 2 - sqrt(3) [the Frobenius automorphism] and so alpha^(p+1) = 1. Thus 6 divides p + 1 and so p = 5 (mod 12). In brief then p = 1 or 5 (mod 12). Take n to be even. Then alpha^(n/2) has order 12 in k^* and so 12 divides p + 1 if p = 5 (mod 12). This is impossible, so for even n we have p = 1 (mod 12) or p = 1 or 13 (mod 24). Finally suppose that n is odd. We need congruences for alpha^((p +- 1)/2). Set beta = 1 + sqrt(3). Then beta^2 = 2 alpha. If p = 1 (mod 12) then 1 = beta^(p-1) = 2^((p-1)/2) alpha^((p-1)/2) and so in k^* we have alpha^((p-1)/2) = (2/p) [this is a Legendre symbol]. If p = 5 mod 12 then beta^p = 1 - sqrt(3) and beta^(p+1) = -2. Hence -2 = 2^((p+1)/2) alpha^((p+1)/2) and so alpha^((p+1)/2) = - (2/p). We wish to show that p = 1 (mod 8); if this fails then (2/p) = -1 so let's assume this occurs. If p = 1 (mod 12) then alpha^((p-1)/2) = -1 and so alpha^((p-1)/4) has order 4. As n is odd then alpha^(3n(p-1)/4) has order 4, but it equals (-1)^((p-1)/4): contradiction. If p = 5 (mod 12) then alpha^((p+1)/2) = 1 and so alpha^(3n(p+1)/2) = 1. But (p+1)/2 is odd and so alpha^(3n(p+1)/2) = (-1)^((p+1)/2) = -1: contradiction. Hence p = 1 (mod 8) and p = 1 or 17 (mod 24). > 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. The period of s[n] modulo p is the order of alpha in k^*, since s[n] = 2 (mod p) iff alpha^n - 2 + alpha^n = 0 in k^* iff alpha^n - 1 = 0. If the period of alpha is 6n then alpha^n has order 6 in k^* and so alpha^n is a root of X^2 - X + 1 = 0 and alpha^n + alpha^(-n) = 1 in k^*. We have seen that if p | s[n] - 1 then alpha^n has order 6 and so alpha's order is a multiple of 6. Robin Chapman + "They did not have proper Department of Mathematics - palms at home in Exeter." University of Exeter, EX4 4QE, UK + rjc@maths.exeter.ac.uk - Peter Carey, http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum