Another (candidate) test of primality of Mersenne number

  • Thread starter T.Rex
  • Start date
  • #1
62
0
Hi,

You probably already know the Lucas-Lehmer-Test (LLT) used for proving that a Mersenne number is prime or composite. (See: http://mathworld.wolfram.com/Lucas-LehmerTest.html" [Broken]).

The LLT is based on the properties of the Tree built by [tex]x^2-2[/tex] modulo a Mersenne number.

Now, here is a conjecture (checked up to M26 = [tex]M_{23209}[/tex]) based on the properties of the Cycles of length (q-1) built by [tex]x^2-2[/tex] modulo a Mersenne number.

[tex]\large M_q=2^q-1 \text{ is prime } \Longleftrightarrow \ S_{q-1} \equiv S_0 \ \pmod{M_q} \text{ , where: } S_0=3^2+1/3^2 , \ S_{i+1}=S_i^2-2 \ .[/tex]

How can it be proved ?

Tony
(far from Internet till 8th of May)
 
Last edited by a moderator:

Answers and Replies

  • #2
62
0
No idea ?

This conjecture is the first step of an attempt to find a primality proof for Mersenne numbers faster than the Lucas-Lehmer test (LLT).
So a proof could help the GIMPS project.

Tony
 
  • #3
841
0
T.Rex said:
[tex]M_q[/tex] is a Mersenne number.

[tex]\large M_q=2^q-1 \text{ is prime } \Longleftrightarrow \ S_{q-1} \equiv S_0 \ \pmod{M_q} \text{ , where: } S_0=3^2+1/3^2 , \ S_{i+1}=S_i^2-2 \ .[/tex]

How can it be proved ?

Tony
(far from Internet till 8th of May)

I not sure how to do mod arithmetic in fractions.
Let
Say [tex]M_q = 7 = 63/9[/tex] and[tex]S_{0} = \frac{82}{9}[/tex]
1) Is the following true?
[tex]S_0 \equiv \frac{(82-63)}{9} = \frac{19}{9} \mod M_q[/tex]

2)If S_0 is squared the denominator gets larger, but how does it then become equal to [tex]9[/tex] again?

3)Can you illustrate this for M_2 or M_3?
 
Last edited:
  • #4
62
0
ramsey2879 said:
I not sure how to do mod arithmetic in fractions...
1/3^2 mod Mq can be easily computed, since Mq=1+2.3.q.k .
1/3 mod Mq = (2.Mq+1)/3 .

Examples with q=5, 7, 13 (using PARI/gp) :
q=5
(1/3)%31 --> 21
(2*31+1)/31 --> 21
(3^2+1/3^2)%31 --> 16

q=7
(1/3)%127 --> 85
(2*127+1)/3 --> 85
(3^2+1/3^2)%127 --> 122

q=13
(1/3)%8191 --> 5461
(2*8191+1)/3 --> 5461
(3^2+1/3^2)%8191 --> 7290

Regards,

Tony
 
  • #5
62
0
Iterations for q=5,7,11,13 and PARI/gp code

Code:
q=5: S0=16 -> 6 -> 3 -> 7 -> 16

q=7: S0=122 -> 23-> 19 -> 105 -> 101 -> 39 -> 122

q=11: S0=464 -> 359 -> 1965 -> 581 -> 1851 -> 1568 -> 175 -> 1965 -> 581 -> 1851 -> 1568

q=13: S0=7290 -> 890 -> 5762 -> 2519 -> 5525 -> 5957 -> 2435 -> 7130 -> 3552 -> 2562 -> 2851 -> 2727 -> 7290

PARI/gp:

LLGT(q)=
{
M=2^q-1; S0=(3^2+1/3^2)%M; print(S0); S=S0;
for(i=1, q-1, S=(S^2-2)%M; print(S));
if(S==S0, print("Prime !"), print("Composite"))
}
 
  • #6
62
0
T.Rex said:
This conjecture is the first step of an attempt to find a primality proof for Mersenne numbers faster than the Lucas-Lehmer test (LLT).
I forgot to say that the idea could only speed up proving a Mersenne number is composite.
T.
 
  • #7
841
0
T.Rex said:
1/3^2 mod Mq can be easily computed, since Mq=1+2.3.q.k .
1/3 mod Mq = (2.Mq+1)/3 .

Examples with q=5, 7, 13 (using PARI/gp) :
q=5
(1/3)%31 --> 21
My excel program gives 1/3 mod 31 = .333 which seems correct to me.
T.Rex said:
(2*31+1)/31 --> 21
Why not (2*31+1)/31 = 3?
 
  • #8
841
0
T.Rex said:
Code:
q=5: S0=16 -> 6 -> 3 -> 7 -> 16

q=7: S0=122 -> 23-> 19 -> 105 -> 101 -> 39 -> 122

q=11: S0=464 -> 359 -> 1965 -> 581 -> 1851 -> 1568 -> 175 -> 1965 -> 581 -> 1851 -> 1568

q=13: S0=7290 -> 890 -> 5762 -> 2519 -> 5525 -> 5957 -> 2435 -> 7130 -> 3552 -> 2562 -> 2851 -> 2727 -> 7290

PARI/gp:

LLGT(q)=
{
M=2^q-1; S0=(3^2+1/3^2)%M; print(S0); S=S0;
for(i=1, q-1, S=(S^2-2)%M; print(S));
if(S==S0, print("Prime !"), print("Composite"))
}
Could you work these through to show how one would get a integer as the result using pencil and paper instead of a fraction when you compute [tex]S_{0} (or 9 + 1/9) mod 7[/tex]
 
  • #9
62
0
ramsey2879 said:
My excel program gives 1/3 mod 31 = .333 which seems correct to me. Why not (2*31+1)/31 = 3?
It is Arithmetic. Use an appropriate tool, like PARI/gp.
Here y=1/x=x^(-1) mod z means y*x = 1 mod z , where x, y and z are integers ....
T.
 
  • #10
62
0
ramsey2879 said:
Could you work these through to show how one would get a integer as the result using pencil and paper instead of a fraction when you compute [tex]S_{0} (9 + 1/9) mod 7[/tex]
Since 9 = 2 mod 7 and since 2*4=8=1 mod 7 , 9+1/9 = 2+1/2=2+4=6 mod 7.
T.
 
  • #11
841
0
OK Now I understand how fractions can be converted to integers in mod calculations.
[tex]1/9= 1/2 = 8/2 = 4 \mod 7[/tex]

Thanks
 
  • #12
841
0
I thimk you and I have something

I can't begin to proove it but you seem to have something here.
P.S. How about my test?
If [tex]M_{p}[/tex] is prime, then for the recursive series [tex]S_{1}=a, S_{2} = b,[/tex]
[tex] S_{n} = 6*S_{(n-1)} - S_{(n-2)} \mod M_{p} \quad \mid 0 \leq a,b < M_{p}[/tex]
Then [tex]S_{2^{(p-1)}} = a[/tex]

For [tex]m_{p}[/tex] = composite the test is not conclusive for a single a and b but it is easy to find a false set.
 
Last edited:

Related Threads on Another (candidate) test of primality of Mersenne number

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