## LLT numbers

Let's say: $$L(x)=x^2-2$$ , $$L^1 = L$$, $$L^m = L \circ L^{m-1} = L \circ L \circ L \ldots \circ L$$.
Where $$L(x)$$ is the polynomial used in the Lucas-Lehmer Test (LLT) :
$$S_0=4 \ , \ S_{i+1}=S_i^2-2=L(S_i) \ ; \ M_q \text{ is prime } \Longleftrightarrow \ S_{q-2} \equiv 0$$ modulo $$M_q$$ .

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

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

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

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

T.

 PhysOrg.com science news on PhysOrg.com >> 'Whodunnit' of Irish potato famine solved>> The mammoth's lament: Study shows how cosmic impact sparked devastating climate change>> Curiosity Mars rover drills second rock target

Recognitions:
Homework Help
 Quote by T.Rex How to prove it ? (I have no idea ...) T.
Induction?

 Recognitions: Gold Member Science Advisor Staff Emeritus If that pattern of alternating signs keeps up, oberve that $$C_m^+ = \frac{L^m(i) + L^m(1)}{2}$$

## LLT numbers

OK. I've got a proof. Thanks for the hints! Not so difficult once you think using "i" !
T.

 Now, more difficult, I think. Can you prove: $$\prod_{i=1}^{2^n-1}C_i^{+} \equiv 1 \pmod{F_n}\ \$$ iff $$\ \ F_n=2^{2^n}+1$$ is prime. T.
 Can you prove: $$C_{2^n}^{+} \equiv -2 \pmod{F_n} \ \Longleftrightarrow \ F_n=2^{2^n}+1 \text{ is prime.}$$. T.

 Quote by T.Rex Can you prove: $$C_{2^n}^{+} \equiv -2 \pmod{F_n} \ \Longleftrightarrow \ F_n=2^{2^n}+1 \text{ is prime.}$$. 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?

Hello,
 Quote by Playdo 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:
Generalized Pell Numbers: Zhi-Wei SUN helped me.
New properties of Mersenne numbers: an anonymous reviewer provided a nice proof.
Cycles under the LLT modulo a Mersenne prime: 2 guys helped me, including ZetaX from this forum.
Regards,
Tony

 Quote by T.Rex Can you prove: $$C_{2^n}^{+} \equiv -2 \pmod{F_n} \ \Longleftrightarrow \ F_n=2^{2^n}+1 \text{ is prime.}$$. T.
I think I have an idea.
It appears that we have: $$L^m(i) = V_{2^m}(1,-1)$$, where i is the square root of -1, m is greater than 1, and $$V_n(1,-1)$$ is a Lucas number defined by: $$V_0=2 , V_1=1, V_{n+1}=V_n+V_{n-1}$$. Look at "The Little Book of BIGGER primes" by Paulo Ribenboim, 2nd edition, page 59.
So, what I called LLT numbers are: $$C_m^+ = \frac{V_{2^m}-1}{2}$$.
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

 Recognitions: Gold Member Science Advisor Staff Emeritus 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.

 Quote by Hurkyl ... but also for doubling the indices.
Yes: $$V_{2n}=V_n^2-2Q^n$$.
When n is even and Q=-1 or 1, we have: $$V_{2^n}=V_{2^{n-1}}^2-2$$ 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.

 Recognitions: Gold Member Science Advisor Staff Emeritus IIRC, there's a more general one. If you know $U_m, U_{m+1}, V_m, V_{m+1}$, you can leap directly to $U_{2m}, U_{2m+1}, V_{2m}, V_{2m+1}$. 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!