Chris Nash <[EMAIL PROTECTED]> wrote:
> Define L(n)=(2+sqrt(3))^n+(2-sqrt(3))^n. It turns out that what we usually
> call *the* Lucas sequence is just
>
> S(n)=L(2^n).
Yes. We can check S(0) = L(1) = 4 and S(n+1) = S(n)^2 - 2
from the definitions. So S defines the familiar Lucas sequence.
> The whole point of the proof is to show that the set of elements a+b.sqrt(3)
> (a, b mod N) that form a closed group under multiplication has the maximal
> order, N^2-1, and thus N is prime. The Lucas sequence does this with a
> little jiggery-pokery, because it is sufficient to show that L(N+1) is zero,
> while L((N+1)/q) isn't for any prime factor q of N+1. For Mersenne numbers
> the only factor to worry about is 2, so the test collapses into its briefer
> form.
> So the question becomes one of solving (2+sqrt(3))^n has zero surd part, and
> in fact prove that the group does not have order N^2-1. The sequence L(n)
> "will" recur in that case. However, it is not difficult to prove that the
> "first" recurrence, ie the point where L(x)=L(1), will generally occur quite
> late in the sequence unless N has all small factors - in which case, we
> would have eliminated this N by trial factoring.
> Remember too, this is late in the "L" sequence, not in the S sequence!
> Suppose for instance it occurred between L(2^(n-3)) and L(2^(n-2)) - which,
> even assuming the "first" recurrence is equally likely anywhere, would occur
> with probability 50%. The S-sequence would not even see it.
We can illustrate working modulo M23 = 8388607 = 47 * 178481.
3 is a quadratic reside modulo 47 (e.g, 12^2 == 3 mod 47),
so 2 + sqrt(3) is in the base field of order 47.
The multiplicative order of 2 + sqrt(3) divides 47-1, and turns out to be 23.
3 is a quadratic nonresidue modulo q = 178481. The order of 2 + sqrt(3)
divides q + 1 = 178482 = 2 * 3 * 151 * 197 and turns out to be 178482.
The least common multiple of these orders is
2 * 3 * 23 * 151 * 197. So L(2 * 3 * 23 * 151 * 197) == L(0) mod M23.
For the L sequence, we need two powers of 2 whose difference is
divisible by 2 * 3 * 23 * 151 * 197.
The orders of 2 modulo 3, 23, 151, 197 are 2, 11, 15, 196, respectively.
The order of 2 modulo 3 * 23 * 151 * 197 is the least common multiple
of these orders, namely 2^2 * 3 * 5 * 7^2 * 11 = 32340.
To include a factor of 2, we need L(2^32341) == L(2^1) mod M23.
That is, S(32341) == S(1) mod M23.
This is far more than 23 LL steps before the sequence repeats.
EXERCISE: Repeat this analysis modulo M11 = 23 * 89.
Find the period modulo M29 = 233 * 1103 * 2089, after getting
the individual periods for each prime factor.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
