- **Math**
(*https://www.mersenneforum.org/forumdisplay.php?f=8*)

- - **A property of prime Mersenne numbers under LLT**
(*https://www.mersenneforum.org/showthread.php?t=4650*)

A property of prime Mersenne numbers under LLTHi,
I've found (by computation) a property that looks interesting. This property applies only to Mersenne numbers [tex]M_q[/tex] such that [tex]q \equiv 1 \pmod{4}[/tex]. 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: [tex]R^2-2 \equiv -(R+1) \pmod{M_q}[/tex] (1) [tex](R+1)^2-2 \equiv R \pmod{M_q}[/tex] (2) [tex]R*(R+1) \equiv 1 \pmod{M_q}[/tex] (3) q=5 -> R=12 q=13 -> R=394 q=17 -> R=41127 For q=29 there are 4 numbers R such that [tex]R^2-2 \equiv -T \pmod{M_q}[/tex] and [tex]T^2-2 \equiv R \pmod{M_q}[/tex] : 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 |

PARI/gp codeA 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 . |

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 |

A clearer conjecture[QUOTE=cyrix]Your Conjecture is false![/QUOTE] 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. [/QUOTE] 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: [tex]\ \ \ R^2+R-1 \equiv 0 \ \ \pmod{M_q}[/tex] (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! [/QUOTE] Not really. Since [tex]18 \equiv -13 = -(12+1) \ \ \pmod{M_q}[/tex] 18 is the "same" solution than 12. In fact, if you replace R by -(R+1) in property (P), you have: [tex](-(R+1))^2+(-(R+1))-1 = R^2+2R+1-R-2=R^2+R-1[/tex] . So, if R is a solution of (P), then -(R+1) is also a solution. So I propose to reformulate the conjecture: For [tex]\ q \equiv 1\ \ \pmod{M_q}[/tex] , if there exists one and only one number R that verifies the property (P), then [tex]M_q[/tex] 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 |

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

I do not understand the linkHi 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 |

sorry Tony!
I messed something up. Now in a better form: [QUOTE=cyrix]Hi T.Rex! For prime [tex]M_q[/tex] with [tex] q \equiv 1 \pmod 4 [/tex] (and q>1) your conjecture is true: Because of the quadratic reciprocity law (Gauß) 5 is a quadratic residue of [tex] M_q [/tex], iff [tex] M_q [/tex] is quadratic NON residue of 5 (because 5=4*1+1 and [tex] M_q=4*n+3 [/tex]). [/QUOTE] [tex] M_q \equiv 3 \pmod 4 [/tex], but since [tex] 5 \equiv 1 \pmod 4[/tex] the reciprocity law works in the same way, So you can find a solution X with [tex] X^2 \equiv 5 \pmod {M_q} [/tex]. This means, you can find the two solutions R_1 and R_2 with [tex] R^2+R-1 \equiv 0 \pmod {M_q} [/tex] because of the formel in my first post. (with the second solution [tex] Y^2 \equiv 5 \pmod {M_q} [/tex] you get the same solutions R_2, R_1) Your conjecture reduces to: 5 is a quadratic residue of [tex] M_q [/tex] with q a prime and [tex] q \equiv 1 \pmod 4 [/tex], iff [tex] M_q[/tex] is prime itself. Yours, Cyrix |

Clear nowOK. 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. [tex]q \equiv 1 \ \pmod{4} , \ M_q\text{ is prime } \Longleftrightarrow \ \ 5^{\frac{M_q-1}{2}} \ \equiv \ 1 \ \ \pmod{M_q} [/tex] Your opinion ? Tony |

In the End: Your (second) Conjecture is false, sorryHi Tony!
For q=53 we have [tex]M_q=6,361 \cdot 69,431 \cdot 20,394,401 [/tex], for all of these primefactors 5 is a quadratic residue, so 5 is also a quadratic residue of [tex]M_q=M_{53} [/tex], so this is a counter example for the conjecture, that there exists exactly two solutions of [tex] R^2+R-1 \equiv 0 \pmod {M_q}[/tex] for prime q>1 and q=4n+1. EDIT: But your last statement holds for q=53: [tex] 5^{\left(\left(2^{53}-1\right)-1\right)/2} \equiv 6,364,152,535,243,836 \pmod {2^{53}-1} [/tex], means: [tex]M_{53}[/tex] is not a prime. Cyrix |

[QUOTE=T.Rex]
[tex]q \equiv 1 \ \pmod{4} , \ M_q\text{ is prime } \Longleftrightarrow \ \ 5^{\frac{M_q-1}{2}} \ \equiv \ 1 \ \ \pmod{M_q} [/tex] Tony[/QUOTE] We proved the "[tex]\Rightarrow[/tex]", the "[tex]\Leftarrow[/tex]" 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 |

LLT and Pépin tests are for Mersenne and Fermat numbers ! (I think)[QUOTE=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[/QUOTE] 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 [tex]llt(x)=x^2-2 \ \pmod{N}[/tex] 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 [tex]L_0=3[/tex] and do the test q-2 times, then [tex]L_{q-2}=3[/tex] if M_q is prime (q=1 (mod 4) . If you start with [tex]L_0=2^{\frac{q+1}{2}}-1[/tex] then you get [tex]L_{q-2}[/tex] 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 |

[QUOTE=T.Rex]
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 ? [/QUOTE] These two statements are related, yes. But the 5^... is stronger, because it uses the litte Fermat, too. For q=53 the number 5 is a quadratic residue, but M_q does not hold a fermat-test with base 5. Cyrix |

Pépin's test proved by means of LLT meansHi Cyrix,
About what I said about proving that a Pépin's-like test can be used for Mersenne numbers, look at the bottom of page 4 of this [URL=http://tony.reix.free.fr/Mersenne/PrimalityTest1FermatNumbers.pdf]paper[/URL], which clearly shows that one can prove the Pépin's test (with k=3) for Fermat numbers by means of technics developped by Lucas and refined by Ribenboim for Mersenne numbers, and that I generalized and applied to Fermat numbers. So I guess the same could be done (with k=5) for Mersenne numbers. The problem is to find the appropriate Lucas Sequence, I think. Tony |

All times are UTC. The time now is 03:00. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.