Another (candidate) test of primality of Mersenne number

[T.Rex]

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

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

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

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

How can it be proved ?

Tony
(far from Internet till 8th of May)

 

[T.Rex]

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

 

[ramsey2879]

M_q is a Mersenne number.

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

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 M_q = 7 = 63/9 andS_{0} = \frac{82}{9}
1) Is the following true?
S_0 \equiv \frac{(82-63)}{9} = \frac{19}{9} \mod M_q

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

3)Can you illustrate this for M_2 or M_3?

 

[T.Rex]

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

 

[T.Rex]

Iterations for q=5,7,11,13 and PARI/gp 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"))
}

 

[T.Rex]

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.

 

[ramsey2879]

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.

(2*31+1)/31 --> 21

Why not (2*31+1)/31 = 3?

 

[ramsey2879]

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 S_{0} (or 9 + 1/9) mod 7

 

[T.Rex]

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.

 

[T.Rex]

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 S_{0} (9 + 1/9) mod 7

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.

 

[ramsey2879]

OK Now I understand how fractions can be converted to integers in mod calculations.
1/9= 1/2 = 8/2 = 4 \mod 7

Thanks

 

[ramsey2879]

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 M_{p} is prime, then for the recursive series S_{1}=a, S_{2} = b,
S_{n} = 6*S_{(n-1)} - S_{(n-2)} \mod M_{p} \quad \mid 0 \leq a,b < M_{p}
Then S_{2^{(p-1)}} = a

For m_{p} = composite the test is not conclusive for a single a and b but it is easy to find a false set.