20210312, 01:04  #12  
Feb 2017
Nowhere
2^{4}×3×7×19 Posts 
Quote:
For example, (5/Mp) = +1 if Mp is prime and p == 1 (mod 4), but (5/Mp) = 1 if Mp is prime and p == 3 (mod 4). (IIRC this came up in a test devised by Lucas, but I'm too lazy to track it down.) 

20210312, 03:09  #13  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2830_{16} Posts 
Quote:
Long time ago I believed that mersenne factors behave in some similar way to fermat numbers (there are many reasons why that should be), and some similar "pepin test" would work for them (which is essentially a 3PRP test), but I could not prove it. That would mean a 3prp test, eventually with a "small tweak", could show if a cofactor is composite or not. Such "trick" would have been very useful and extremely valuable for our cofactoring ("disbelievers...") thread and people who do the PRPCF work. Unfortunately, I was wrong, or just unable to find the "tweak". That's how we all learn... Here is a discussion about rarity of PSP numbers (read following 34 posts too, before RDS jumped in and killed everybody ), and here is an example of a 3PSP cofactor (i.e. it is 3PRP, but still composite). There are not many of those, but they are enough. Some "didactic" implementation of a PSPfinder that also popped up with the search, and some may find it useful, is here (hey, don't jump to my head, it is didactic, i.e. to teach how it is done, not an optimized one!) Edit: Here is another post which made it through the search filter. I would put it in a frame (the post, not the filter!) and stick it on a wall for the beginners who join the forum and ask the same questions again and again (HA! in the past I was more clever, and I had more patience, I totally forgot I was posting things like that on the forum ) Last fiddled with by LaurV on 20210312 at 04:03 

20210312, 08:16  #14 
Feb 2017
Belgium
15_{16} Posts 
So thereexists no proof nor counterexample for a=3 yet? A proof is still possible?
“If (3^(Mn1)/2+ 1)==0 (mod Mn) then Mn is prime”. It may still be possible to prove this. And it's worthwhile If itstands, I believe it’s possible to speed up some calculations. If I read well there are still some "strong believers" to it 
20210312, 11:28  #15 
Feb 2017
Belgium
3·7 Posts 
Now, I am trying to prove whether there exists some kind of induction for the Catalan sequence 3, 7, 127, … (if Ci divides 3^(Ci1)/2 + 1==0 (mod Ci) for i=n,n+1,n+2 then it holds for i=n+3 or something like that) or a kind of maximum number of iterations f.e. 5. But I am not that strong with modulo calculations. I do notice some things running small macro’s.
I believe there is no MMn when there’s a r<n/4 for which 3^r + 1 == 0 (mod Mn), f.e. 3^445 + 1 == 0 (mod M13). The same goes for M31. Note, it can been proved in less than 10 steps that M12 is prime (if my assumption stands). This might be equivalent to the zero’s appearing in the sequence 2^k1 == 0 (mod Mn) for n=11 and k < Mn1. Even if my assumption doesn’t stand it might be interesting if someone can give a feedback on the observations I made. Persons strong in modulo calculus certainly can give quickly some comments. 
20210312, 14:12  #16  
Feb 2017
Nowhere
2^{4}×3×7×19 Posts 
Quote:
Conversely, if Mod(3, P)^((P1)/2) = Mod(1,P) then Mod(3,P) has multiplicative order exactly P1, so P is prime. The situation for Mersenne numbers is alas more complicated. We know that if p > 2 is prime, any prime factor q of 2^p  1 is of the form q = 2*k*p + 1. This means that all the q1 have the common factor 2*p, which is also a factor of any product of the q's minus 1. (As axn already noted back when) Since the exact multiplicative order of 2 (mod q) is always p, and p divides q1 for every q, you can be sure that any product of the q's is a base2 Fermat pseudoprime. It is also easy to see that any such product will "pass" the Euler test. If we want a product of q's to be a base3 Fermat pseudoprime, we want the lcm of the znorder(Mod(3, q)) to divide the product of the q's minus 1. For the factors 1913 and 5737 of M239 (Thank you very much!) we have 1913 = 2*4*239 + 1 and 5737 = 2*12*239 + 1. The gcd of the q1 values is 8*239. It happens that znorder(Mod(3, 5737)) = 4*239, which guarantees n = 1913*5737 is a base3 Fermat pseudoprime. Note, however, that Mod(n,12) = Mod(5,12) so kronecker(3,n) == 1, but Mod(3,n)^((n1)/2) == Mod(1, n) so the Euler test detects it as composite. 

20210312, 16:04  #17 
Feb 2017
Belgium
3×7 Posts 
Thx. So 3^(M2391)/2 == 1 (mod M239). It’s not a counterexample to my assumption?

20210312, 17:00  #18 
Feb 2017
Nowhere
2^{4}×3×7×19 Posts 

20210312, 17:50  #19  
Feb 2017
Belgium
15_{16} Posts 
Quote:
Sorry if you take it that way. I didn’t catch the meaning of your post. I know about the q=2kp+1 and Pepin’s test for Fermat numbers. I still believe “If (3^(Mn1)/2 + 1)==0 (mod Mn)then Mn is prime” (Mn being a Mersenne number) is provable (and that I can proof it). If I read well the topics no proof or counterexample exists yet. So a proof is possible. But maybe I made an error somewhere or missed something that already exists. 

20210312, 18:39  #20 
Feb 2017
Belgium
3×7 Posts 
Let me rephrase my original post.
I claim that if (3^(Mn1)/2 + 1)==0 (mod Mn) then Mn is prime. Mn being a Mersenne number. Maybe it holds also for other bases <> 3 (and 2). 
20210312, 18:49  #21 
Feb 2017
Belgium
3·7 Posts 
I spend a lot of time trying to prove it. It was a big puzzle. A few weeks ago I believe to have found the last piece. Maybe I made a mistake along the way, that’s why I am very careful. Verification still has to be done. But is useless to verify if somebody tells it’s not possible or if there exists a counterexample. That means that I have to look for the error(s) …
I am afraid, and nervous :), I made an error somewhere after all … 
20210313, 14:00  #22  
Feb 2017
Nowhere
1100011110000_{2} Posts 
Quote:
I note that the 3PRP test was probably not done on any Mp for which a prime factor q was found during initial factorization attempts. In such a case, it might be possible to prove that Mp is not a 3PRP without actually running the test on Mp itself. If the multiplicative order of Mod(3,q) does not divide Mp  1, then Mp is not a 3PRP. (For example, 2^11  1 = 23*89, and the multiplicative order of Mod(3,89) is 88, which, being divisible by 4, does not divide 2^11  2.) Recognizing the possibility of having made a mistake is a sign of maturity. If you want to know for sure, submit your argument to scrutiny by others. If your argument is wrong, acknowledge it, learn from it, and move on. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Theorems about Mersenne numbers  jnml  Miscellaneous Math  10  20190421 15:33 
Mersenne theorems question  ShiningArcanine  Math  21  20120427 01:38 
Theorems about ideals  fivemack  Abstract Algebra & Algebraic Number Theory  10  20120122 11:01 
new theorems about primes  sghodeif  Miscellaneous Math  18  20060713 18:24 