B.D: Proving C_m^+ in Lucas-Lehmer Test (LLT)

[T.Rex]

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.

 

[CRGreathouse]

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

T.

Induction?

 

[Hurkyl]

If that pattern of alternating signs keeps up, oberve that

$$C_m^+ = \frac{L^m(i) + L^m(1)}{2}$$

 

[T.Rex]

Got it !

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

 

[T.Rex]

LLT numbers and Fermat primes

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.

 

[T.Rex]

Better, simpler

Can you prove:

$$C_{2^n}^{+} \equiv -2 \pmod{F_n} \ \Longleftrightarrow \ F_n=2^{2^n}+1 \text{ is prime.}$$.

T.

 

[Playdo]

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?

 

[T.Rex]

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 learned 30 years ago plus the Number Theory I've learned 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" : Zhi-Wei SUN helped me.
http://tony.reix.free.fr/Mersenne/Mersenne8x3qy.pdf" : an anonymous reviewer provided a nice proof.
http://tony.reix.free.fr/Mersenne/LoopsUnderLLTmodMersennePrime.pdf" : 2 guys helped me, including ZetaX from this forum.
Regards,
Tony

 

[T.Rex]

Lucas numbers

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

 

[Hurkyl]

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.

 

[T.Rex]

... 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.

 

[Hurkyl]

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!