LLT numbers

  • Thread starter T.Rex
  • Start date
  • #1
62
0
Let's say: [tex]L(x)=x^2-2[/tex] , [tex]L^1 = L[/tex], [tex]L^m = L \circ L^{m-1} = L \circ L \circ L \ldots \circ L[/tex].
Where [tex]L(x)[/tex] is the polynomial used in the Lucas-Lehmer Test (LLT) :
[tex]S_0=4 \ , \ S_{i+1}=S_i^2-2=L(S_i) \ ; \ M_q \text{ is prime } \Longleftrightarrow \ S_{q-2} \equiv 0 [/tex] modulo [tex]M_q[/tex] .

We have:
[tex]L^2(x)=x^4-4x^2+2[/tex]
[tex]L^3(x)=x^8-8x^6+20x^4-16x^2+2[/tex]
[tex]L^4(x)=x^{16}-16x^{14}+104x^{12}-352x^{10}+660x^8-672x^6+336x^4-64x^2+2[/tex]

Let's call [tex]C_m^+[/tex] the sum of the positive coefficients of the polynomial [tex]L^m(x)[/tex].
We call [tex]C_m^+[/tex] a "LLT number": [tex]C_1^+ = 1 , C_2^+ = 3 , \ C_3^+ = 23 , \ C_4^+ = 1103 , \ C_5^+ = 2435423 [/tex] .

It seems that we have the formula: [tex]C_m^+ = 2^m \prod_{i=1}^{m-1} C_{i}^+ - 1 \ \ \text{ for: } m>1 [/tex].

How to prove it ? (I have no idea ...)

T.
 
Last edited:

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,824
0
How to prove it ? (I have no idea ...)

T.

Induction?
 
  • #3
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
If that pattern of alternating signs keeps up, oberve that

[tex]
C_m^+ = \frac{L^m(i) + L^m(1)}{2}
[/tex]
 
  • #4
62
0
Got it !

OK. I've got a proof. Thanks for the hints! Not so difficult once you think using "i" !
T.
 
  • #5
62
0
LLT numbers and Fermat primes

Now, more difficult, I think.
Can you prove:

[tex] \prod_{i=1}^{2^n-1}C_i^{+} \equiv 1 \pmod{F_n}\ \ [/tex] iff [tex]\ \ F_n=2^{2^n}+1[/tex] is prime.

T.
 
Last edited:
  • #6
62
0
Better, simpler

Can you prove:

[tex]C_{2^n}^{+} \equiv -2 \pmod{F_n} \ \Longleftrightarrow \ F_n=2^{2^n}+1 \text{ is prime.}[/tex].

T.
 
  • #7
88
0
Can you prove:

[tex]C_{2^n}^{+} \equiv -2 \pmod{F_n} \ \Longleftrightarrow \ F_n=2^{2^n}+1 \text{ is prime.}[/tex].

T.

If it has already been proven then why ask us? If not, do you intend to include our names in the published paper as sources of help?
 
  • #8
62
0
Hello,
If it has already been proven then why ask us ?
I'm an amateur: I play with numbers and try to find nice/interesting properties about nice numbers. I have no proof of this one. I like the way Hurkyl did: he gave an hint and then some of the Maths I learnt 30 years ago plus the Number Theory I've learnt these last years come back and I try to find the proof.
If not, do you intend to include our names in the published paper as sources of help?
Sure. Last year I asked questions in this forum and got answers and proofs and I wrote a paper where I said who helped me. If I write a paper about the LLT numbers, I'll talk about people who helped me. About a "published" paper, my only candidate target is arXiv.org . So, do not dream about being published in a famous journal. My main goal is fun.
As examples, look at:
http://tony.reix.free.fr/Mersenne/GeneralizedPellNumbers.pdf" [Broken]: Zhi-Wei SUN helped me.
http://tony.reix.free.fr/Mersenne/Mersenne8x3qy.pdf" [Broken]: an anonymous reviewer provided a nice proof.
http://tony.reix.free.fr/Mersenne/LoopsUnderLLTmodMersennePrime.pdf" [Broken]: 2 guys helped me, including ZetaX from this forum.
Regards,
Tony
 
Last edited by a moderator:
  • #9
62
0
Lucas numbers

Can you prove:

[tex]C_{2^n}^{+} \equiv -2 \pmod{F_n} \ \Longleftrightarrow \ F_n=2^{2^n}+1 \text{ is prime.}[/tex].

T.
I think I have an idea.
It appears that we have: [tex]L^m(i) = V_{2^m}(1,-1)[/tex], where i is the square root of -1, m is greater than 1, and [tex]V_n(1,-1)[/tex] is a Lucas number defined by: [tex]V_0=2 , V_1=1, V_{n+1}=V_n+V_{n-1}[/tex]. Look at "The Little Book of BIGGER primes" by Paulo Ribenboim, 2nd edition, page 59.
So, what I called LLT numbers are: [tex]C_m^+ = \frac{V_{2^m}-1}{2}[/tex].
I did not know this relationship.
Now, in order to prove the theorem, I think I could use either the method used by Lehmer or the one used by Ribenboim. I'll see.
Any more ideas ?
Regards,
Tony
 
Last edited:
  • #10
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
There's a U sequence too, I think. There's a nice formula not just for increasing the indices by 1, but also for doubling the indices.
 
  • #11
62
0
... but also for doubling the indices.
Yes: [tex]V_{2n}=V_n^2-2Q^n[/tex].
When n is even and Q=-1 or 1, we have: [tex]V_{2^n}=V_{2^{n-1}}^2-2[/tex] which is the LLT basic formula.
Have I found something useful or is it simply another way to look at an old result ? (Probably second one !)
T.
 
Last edited:
  • #12
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
IIRC, there's a more general one. If you know [itex]U_m, U_{m+1}, V_m, V_{m+1}[/itex], you can leap directly to [itex]U_{2m}, U_{2m+1}, V_{2m}, V_{2m+1}[/itex]. I don't remember the details; I just wanted to throw it out there, in case the idea was useful. The U and V sequences have a ton of useful properties!
 

Related Threads on LLT numbers

  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
3
Views
3K
Replies
6
Views
5K
Replies
4
Views
5K
  • Last Post
Replies
5
Views
4K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
3
Views
5K
  • Last Post
Replies
3
Views
2K
Top