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