20220417, 16:08  #1 
"Καλός"
May 2018
365_{10} Posts 
Mersenne Numbers Known from Number Practice to Be Composite
The Mersenne numbers with prime exponents p > 3 for which p mod 4 = 3 and 2p + 1 is a prime number are known to be composite.
Out of the total of 50,847,534 prime exponents 2 ≤ p ≤ 999,999,937, there are 1,655,600 prime exponents (3.256%) satisfying the aforesaid conditions. Perhaps GIMPS could add notifications that the corresponding Mersenne numbers are known to be composite from elementary number theory. The compressed list of the 1,655,600 prime exponents from 11 to 999,999,191 exceeds the limit of 4 MB. Therefore, a Wolfram code that saves the prime exponents in a file is given below instead. Code:
SetDirectory[NotebookDirectory[]]; fname = NotebookDirectory[] <> "Mp3mod4and2pplus1.dat"; file = File[fname]; If[FileExistsQ[file] == False, OpenWrite[file]; Close[file];]; OpenAppend[file]; Np = PrimePi[999999937]; Pcount = 0; ic = 3; While[ic <= Np, p = Prime[ic]; If[(Mod[p, 4] == 3) && (PrimeQ[2*p + 1] == True), Pcount++; Write[file, p];]; ic++;]; Close[file]; Print[Pcount]; 
20220417, 21:42  #2 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
1101011011100_{2} Posts 
How many don't already have known factors?

20220417, 22:19  #3 
Mar 2019
3·101 Posts 
More precisely, \(2p + 1\) divides \(M_p\) for the case you described. So all of these Mersenne numbers have known (small) factors, and all of them should be in the database already.

20220417, 22:23  #4 
Einyen
Dec 2003
Denmark
110100111100_{2} Posts 
Yes they have the smallest factor 2kp+1 with k=1, so they were found back in ~1996 (or 2008 when the range extended to 1 billion). No "elementary" tricks will improve on a project running for 2526 years.
GIMPS did have major improvements in the last 37 years with Jacobi check, Gerbicz error checking and finally PRP proofs, but they were far from elementary. Last fiddled with by ATH on 20220417 at 22:27 
20220418, 14:06  #5 
"Καλός"
May 2018
5·73 Posts 
The information in this thread is provided for completeness and is not concerned with novelty indeed.
Searching for "1655600", two previous posts on the topic can be located, see https://www.mersenneforum.org/showth...600#post300787 and https://www.mersenneforum.org/showth...600#post180704. 
20220418, 15:42  #6 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
7^{2}×73 Posts 
For p == 3 mod 4, 2*p+1 (if it is prime) always divides 2^p1 (this is even true if p itself is not prime)
There should be conditions that 4*p+1, 6*p+1, 8*p+1, etc. always divides 2^p1 You can check the sequence https://oeis.org/A001917, for q == 1, 7 mod 8, A001917(primepi(q)) is even, and for q == 1, 7 mod 8, A001917(primepi(q)) is odd, thus for p == 3 mod 4, A001917(primepi(2*p+1)) is even, and hence 2*p+1 must divide 2^p1, you can also check that for which prime q, A001917(primepi(q)) is divisible by 3, 4, 5, 6, etc. 
20220418, 16:15  #7  
Mar 2021
France
29_{16} Posts 
Quote:


20220418, 16:37  #8 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
7^{2}·73 Posts 

20220418, 16:41  #9  
Mar 2021
France
101001_{2} Posts 
Quote:
By the way, do you know the condition for example 6*p+1 or 10*p+1 divides 2^p1 ? I know the condition for 2*p+1 but I have no idea for these two for example. 

20220418, 17:15  #10  
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
7^{2}×73 Posts 
Quote:


20220418, 19:25  #11  
Apr 2020
857 Posts 
Quote:
First, you use the phrase "cannot be solved" but you don't understand what it means in this context. Over the reals or the complex numbers, it means that we *literally cannot write down the solutions*. But here we're working over a finite field, namely the integers modulo some prime. So even though it isn't easy to find solutions to x^5 = 2, it is certainly possible to write them down if they exist. And secondly, while a general quintic cannot be solved over the complex numbers, the quintic x^5 = 2 most definitely can! Conditions for 2 to be a quintic residue mod p do exist although they are not convenient to use. This can be done for higher order roots too but the conditions will get even worse. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Repeating residues in LL tests of composite Mersenne numbers  Viliam Furik  Number Theory Discussion Group  22  20201208 14:45 
Mersenne number with exponent 333333367 is composite  TheGuardian  GPU Computing  25  20190509 21:53 
Factoring composite Mersenne numbers using Pollard Rho  jshort  Factoring  9  20190409 16:34 
2 holes in bizarre theorem about composite Mersenne Numbers  wildrabbitt  Math  120  20160929 21:52 
Factoring highly composite Mersenne numbers  philmoore  Factoring  21  20041118 20:00 