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

  • Thread starter T.Rex
  • Start date
  • Tags
    Test
In summary, the Lucas-Lehmer Test (LLT) can be used to determine if a number is prime by looking at the polynomial L(x) and observing that S_0, S_{i+1}, S_i^2-2, and C_m^+ are all prime numbers.
  • #1
T.Rex
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:
Physics news on Phys.org
  • #2
T.Rex said:
How to prove it ? (I have no idea ...)

T.

Induction?
 
  • #3
If that pattern of alternating signs keeps up, oberve that

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

OK. I've got a proof. Thanks for the hints! Not so difficult once you think using "i" !
T.
 
  • #5
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
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
T.Rex said:
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
Hello,
Playdo said:
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
 
Last edited by a moderator:
  • #9
Lucas numbers

T.Rex said:
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
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
Hurkyl said:
... 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
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 to B.D: Proving C_m^+ in Lucas-Lehmer Test (LLT)

What is B.D in the Lucas-Lehmer Test?

B.D refers to the "Basis Definition" step in the Lucas-Lehmer Test. It is the first step in the test and involves selecting a starting value for the sequence.

What does C_m^+ represent in the LLT?

C_m^+ represents the mth term in the Lucas-Lehmer sequence, where m is a prime number. This term is crucial in determining whether the number being tested is a Mersenne prime or not.

What is the purpose of proving C_m^+ in the LLT?

The main purpose of proving C_m^+ in the Lucas-Lehmer Test is to determine if the number being tested is a Mersenne prime or not. If C_m^+ equals 0, then the number is a Mersenne prime, and if it does not equal 0, then the number is not a Mersenne prime.

How is C_m^+ calculated in the LLT?

C_m^+ is calculated by using the Lucas-Lehmer recurrence formula: C_m^+ = (C_m)^2 - 2, where C_m is the previous term in the sequence. This formula is applied repeatedly until the desired mth term is reached.

Can the LLT prove all Mersenne primes?

Yes, the Lucas-Lehmer Test can prove all Mersenne primes. This test has been proven to be accurate for all Mersenne primes discovered to date and has been used to find the largest known prime numbers.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
884
  • Linear and Abstract Algebra
Replies
11
Views
3K
  • Linear and Abstract Algebra
Replies
2
Views
3K
  • Topology and Analysis
Replies
5
Views
3K
  • Topology and Analysis
Replies
1
Views
1K
Replies
7
Views
1K
  • Math Proof Training and Practice
Replies
16
Views
5K
  • Math Proof Training and Practice
2
Replies
64
Views
13K
  • Math Proof Training and Practice
5
Replies
150
Views
15K
  • Math Proof Training and Practice
Replies
28
Views
5K
Back
Top