A property of prime Mersenne numbers under LLT

T.Rex · 2005-09-10, 20:59

Hi,
I've found (by computation) a property that looks interesting.

This property applies only to Mersenne numbers $M_q$ such that $q \equiv 1 \pmod{4}$ .
This properties is true for q=5,13,17 and false for q=29 .
(Why so few examples ? Because it takes hours or days to find these numbers !)

For q=5,13,17, there is a number R that has the following properties:

$R^2-2 \equiv -(R+1) \pmod{M_q}$ (1)

$(R+1)^2-2 \equiv R \pmod{M_q}$ (2)

$R*(R+1) \equiv 1 \pmod{M_q}$ (3)

q=5 -> R=12
q=13 -> R=394
q=17 -> R=41127

For q=29 there are 4 numbers R such that $R^2-2 \equiv -T \pmod{M_q}$ and $T^2-2 \equiv R \pmod{M_q}$ :
874680 , 37882537 , 137237467 , 199174227 .
But T is not equal to R+1 , and R*T (mod M_q) is not equal to 1.

So, I have the following conjecture:

For q=1 (mod 4) , if there exists 1 and only 1 number that verifies properties (1), (2) and (3) , then M_q is prime .

Very nice ! Isn't it ?

The only very small problem is: HOW CAN WE FIND THESE NUMBERS R ?
(I have NO idea yet !)

If one can find the formula that generates R, then we have a VERY fast test for Mersenne numbers ! (but I guess the cost of finding R is comparable to the LLT ... so this would be of no real use.)

Any help is welcome !

Regards,
Tony

T.Rex · 2005-09-10, 21:18

A simple PARI/gp code for finding R is :

q=13;M=2^q-1
for(i=1,(M-1)/2, j=(i^2-2)%M; if((M-j)==i+1, print(i)))

For a great M, one should start i with a number such that i^2> M .

cyrix · 2005-09-10, 22:54

Hi T.Rex!

Your Conjecture is false!

All conditions are equal: R^2+R-1=0 mod M, this means R_{1/2}= -1/2 +- \sqrt{1/4+1}= (-1+-sqrt(5))/2.

For q=5 we have M=31 and sqrt(5)= +-6, thus we have R_1=(-1-6)/2=12 AND R_2=(-1+6)/2=18. So For M=31 R_2=18 is also a solution!

Cyrix

T.Rex · 2005-09-11, 09:30

Quote:

Originally Posted by cyrix

Your Conjecture is false!

Not really. It was unclear on some points and not reduced. Thanks for your help !

Quote:

All conditions are equal: R^2+R-1=0 mod M, this means R_{1/2}= -1/2 +- \sqrt{1/4+1}= (-1+-sqrt(5))/2.

You are perfectly right !
I found this too after I switched off my PC and read my post quietly.
That means properties (1), (2) and (3) are the same:

$\ \ \ R^2+R-1 \equiv 0 \ \ \pmod{M_q}$ (P) .

Quote:

For q=5 we have M=31 and sqrt(5)= +-6, thus we have R_1=(-1-6)/2=12 AND R_2=(-1+6)/2=18. So For M=31 R_2=18 is also a solution!

Not really.
Since $18 \equiv -13 = -(12+1) \ \ \pmod{M_q}$ 18 is the "same" solution than 12.
In fact, if you replace R by -(R+1) in property (P), you have: $(-(R+1))^2+(-(R+1))-1 = R^2+2R+1-R-2=R^2+R-1$ .
So, if R is a solution of (P), then -(R+1) is also a solution.

So I propose to reformulate the conjecture:

For $\ q \equiv 1\ \ \pmod{M_q}$ , if there exists one and only one number R that verifies the property (P), then $M_q$ is prime.
-(R+1) is called the dual solution of (P).

Do you agree with this new conjecture ?

Now, we have 2 problems:
- provide a proof !
- find a way to build this mysterious number R !

Help is welcome !

Also, finding R for other q would be great !
But the next one is: 89 . It may take months or years of computation before finding R_89 ...

Regards,
Tony

cyrix · 2005-09-11, 10:47

Hi T.Rex!

For prime $M_q$ with $q \equiv 1 \pmod 4$ (and q>1) your conjecture is true: Because of the quadratic reciprocity law (Gau�) 5 is a quadratic residue of $M_q$ , iff $M_q$ is quadratic residue of 5 (because both are of the from 4n+1). But $M_q=2^q-1=2^{4n+1}-1 \equiv 2^1-1=1^2 \pmod 5$ so 5 is a quadratic residue of $M_q$ and there existists two numbers X and Y, which have the properties $X \equiv -Y \pmod {M_q}$ and $x^2 \equiv y^2 \equiv 5 \pmod {M_q}$

Yours,
Cyrix

T.Rex · 2005-09-11, 13:21

Hi Cyrix,
Sorry, I do not see the link between (5/M_q) and the conjecture.

I know the quadratic reciprocity and I understand your explanations.
But, are you saying that M_q is of the form 4n+1 ?

What is the link between (5/M_q) and what I said ?

Tony

cyrix · 2005-09-11, 15:00

sorry Tony!
I messed something up. Now in a better form:

Quote:

Originally Posted by cyrix

Hi T.Rex!

For prime $M_q$ with $q \equiv 1 \pmod 4$ (and q>1) your conjecture is true: Because of the quadratic reciprocity law (Gau�) 5 is a quadratic residue of $M_q$ , iff $M_q$ is quadratic NON residue of 5 (because 5=4*1+1 and $M_q=4*n+3$ ).

$M_q \equiv 3 \pmod 4$ , but since $5 \equiv 1 \pmod 4$ the reciprocity law works in the same way, So you can find a solution X with $X^2 \equiv 5 \pmod {M_q}$ . This means, you can find the two solutions R_1 and R_2 with $R^2+R-1 \equiv 0 \pmod {M_q}$ because of the formel in my first post. (with the second solution $Y^2 \equiv 5 \pmod {M_q}$ you get the same solutions R_2, R_1)

Your conjecture reduces to: 5 is a quadratic residue of $M_q$ with q a prime and $q \equiv 1 \pmod 4$ , iff $M_q$ is prime itself.

Yours,
Cyrix

T.Rex · 2005-09-11, 16:56

OK. I understand your points now.
So, seems we have a conjecture for a P�pin-like test for Mersenne numbers ?!
Is it something new ? I've searched in my books and found nothing.

$q \equiv 1 \ \pmod{4} , \ M_q\text{ is prime } \Longleftrightarrow \ \ 5^{\frac{M_q-1}{2}} \ \equiv \ 1 \ \ \pmod{M_q}$

Your opinion ?

Tony

cyrix · 2005-09-11, 17:30

Hi Tony!

For q=53 we have $M_q=6,361 \cdot 69,431 \cdot 20,394,401$ , for all of these primefactors 5 is a quadratic residue, so 5 is also a quadratic residue of $M_q=M_{53}$ , so this is a counter example for the conjecture, that there exists exactly two solutions of $R^2+R-1 \equiv 0 \pmod {M_q}$ for prime q>1 and q=4n+1.

EDIT: But your last statement holds for q=53:
$5^{\left(\left(2^{53}-1\right)-1\right)/2} \equiv 6,364,152,535,243,836 \pmod {2^{53}-1}$ , means: $M_{53}$ is not a prime.
Cyrix

cyrix · 2005-09-11, 18:51

Quote:

Originally Posted by T.Rex

$q \equiv 1 \ \pmod{4} , \ M_q\text{ is prime } \Longleftrightarrow \ \ 5^{\frac{M_q-1}{2}} \ \equiv \ 1 \ \ \pmod{M_q}$
Tony

We proved the " $\Rightarrow$ ", the " $\Leftarrow$ " is true for all prime q=4n+1<3000 (I tested it with Maple).

But even when this is a real test (and the equvialence is true), it would cost as much time as a LL-Test would do...

Cyrix

T.Rex · 2005-09-11, 19:36

Quote:

Originally Posted by cyrix

But even when this is a real test (and the equivalence is true), it would cost as much time as a LL-Test would do... Cyrix

Yes, I know about the cost. But it seems interesting to be able to say that a P�pin's like test applies to Mersenne numbers. I (and Lucas before) provided LLT-like tests for Fermat numbers.
Many people think that LLT is for Mersenne numbers (N-1) and that P�pin's test is for Fermat numbers (N+1). I think it is interesting to be able to say that these 2 tests can apply both to N-1 or N+1 numbers. (done for LLT)

I've studied the LLT function $llt(x)=x^2-2 \ \pmod{N}$ with Mersenne numbers and other numbers and found interesting properties. But I must write down this since 1 or 2 years ...
About Mersenne numbers, some of these properties have been described before by Shanks. But, since he said "prove it if you can", I'm not sure he had a proof !
As an example of these properties, if you start the LLT with $L_0=3$ and do the test q-2 times, then $L_{q-2}=3$ if M_q is prime (q=1 (mod 4) .
If you start with $L_0=2^{\frac{q+1}{2}}-1$ then you get $L_{q-2}$ has the same value as L_0 if M_q is prime, for any prime q.

About q=53 I don't understand how 1 statement is true (5^...) though the other one is false (R^2+R-1 ...) since they are related. Do you ?

I really appreciate our discussion !

Tony

2005-09-10, 20:59	#1
T.Rex Feb 2004 France 937 Posts	A property of prime Mersenne numbers under LLT Hi, I've found (by computation) a property that looks interesting. This property applies only to Mersenne numbers $M_q$ such that $q \equiv 1 \pmod{4}$ . This properties is true for q=5,13,17 and false for q=29 . (Why so few examples ? Because it takes hours or days to find these numbers !) For q=5,13,17, there is a number R that has the following properties: $R^2-2 \equiv -(R+1) \pmod{M_q}$ (1) $(R+1)^2-2 \equiv R \pmod{M_q}$ (2) $R(R+1) \equiv 1 \pmod{M_q}$ (3) q=5 -> R=12 q=13 -> R=394 q=17 -> R=41127 For q=29 there are 4 numbers R such that $R^2-2 \equiv -T \pmod{M_q}$ and $T^2-2 \equiv R \pmod{M_q}$ : 874680 , 37882537 , 137237467 , 199174227 . But T is not equal to R+1 , and RT (mod M_q) is not equal to 1. So, I have the following conjecture: For q=1 (mod 4) , if there exists 1 and only 1 number that verifies properties (1), (2) and (3) , then M_q is prime . Very nice ! Isn't it ? The only very small problem is: HOW CAN WE FIND THESE NUMBERS R ? (I have NO idea yet !) If one can find the formula that generates R, then we have a VERY fast test for Mersenne numbers ! (but I guess the cost of finding R is comparable to the LLT ... so this would be of no real use.) Any help is welcome ! Regards, Tony Last fiddled with by T.Rex on 2005-09-10 at 21:05

2005-09-10, 21:18	#2
T.Rex Feb 2004 France 937 Posts	PARI/gp code A simple PARI/gp code for finding R is : q=13;M=2^q-1 for(i=1,(M-1)/2, j=(i^2-2)%M; if((M-j)==i+1, print(i))) For a great M, one should start i with a number such that i^2> M .

2005-09-11, 13:21	#6
T.Rex Feb 2004 France 3A9₁₆ Posts	I do not understand the link Hi Cyrix, Sorry, I do not see the link between (5/M_q) and the conjecture. I know the quadratic reciprocity and I understand your explanations. But, are you saying that M_q is of the form 4n+1 ? What is the link between (5/M_q) and what I said ? Tony

2005-09-11, 16:56	#8
T.Rex Feb 2004 France 937 Posts	Clear now OK. I understand your points now. So, seems we have a conjecture for a P�pin-like test for Mersenne numbers ?! Is it something new ? I've searched in my books and found nothing. $q \equiv 1 \ \pmod{4} , \ M_q\text{ is prime } \Longleftrightarrow \ \ 5^{\frac{M_q-1}{2}} \ \equiv \ 1 \ \ \pmod{M_q}$ Your opinion ? Tony

2005-09-11, 17:30	#9
cyrix Jul 2003 Thuringia; Germany 2×29 Posts	In the End: Your (second) Conjecture is false, sorry Hi Tony! For q=53 we have $M_q=6,361 \cdot 69,431 \cdot 20,394,401$ , for all of these primefactors 5 is a quadratic residue, so 5 is also a quadratic residue of $M_q=M_{53}$ , so this is a counter example for the conjecture, that there exists exactly two solutions of $R^2+R-1 \equiv 0 \pmod {M_q}$ for prime q>1 and q=4n+1. EDIT: But your last statement holds for q=53: $5^{\left(\left(2^{53}-1\right)-1\right)/2} \equiv 6,364,152,535,243,836 \pmod {2^{53}-1}$ , means: $M_{53}$ is not a prime. Cyrix Last fiddled with by cyrix on 2005-09-11 at 17:45

2005-09-10, 22:54	#3
cyrix Jul 2003 Thuringia; Germany 2×29 Posts	Hi T.Rex! Your Conjecture is false! All conditions are equal: R^2+R-1=0 mod M, this means R_{1/2}= -1/2 +- \sqrt{1/4+1}= (-1+-sqrt(5))/2. For q=5 we have M=31 and sqrt(5)= +-6, thus we have R_1=(-1-6)/2=12 AND R_2=(-1+6)/2=18. So For M=31 R_2=18 is also a solution! Cyrix

2005-09-11, 10:47	#5
cyrix Jul 2003 Thuringia; Germany 72₈ Posts	Hi T.Rex! For prime $M_q$ with $q \equiv 1 \pmod 4$ (and q>1) your conjecture is true: Because of the quadratic reciprocity law (Gau�) 5 is a quadratic residue of $M_q$ , iff $M_q$ is quadratic residue of 5 (because both are of the from 4n+1). But $M_q=2^q-1=2^{4n+1}-1 \equiv 2^1-1=1^2 \pmod 5$ so 5 is a quadratic residue of $M_q$ and there existists two numbers X and Y, which have the properties $X \equiv -Y \pmod {M_q}$ and $x^2 \equiv y^2 \equiv 5 \pmod {M_q}$ Yours, Cyrix

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Property of pseudoprime numbers by base 2 AND / OR 3	allasc	And now for something completely different	1	2017-05-17 15:00
new property of prime numbers discovered?	ixfd64	Math	1	2016-03-14 21:53
A conjecture on a new property of Mersenne primes	Thiele	Math	18	2010-05-23 05:35
Curious property of Mersenne numbers.	arithmeticae	Lounge	5	2008-10-27 06:15
A property of Fermat numbers. Already known ?	T.Rex	Math	6	2006-09-17 22:11