Mersenne Numbers Known from Number Theory to Be Composite

[Dobri]

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.

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];

[kriesel]

How many don't already have known factors?

[mathwiz]

Originally Posted by Dobri

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.

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.

[ATH]

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 25-26 years.

GIMPS did have major improvements in the last 3-7 years with Jacobi check, Gerbicz error checking and finally PRP proofs, but they were far from elementary.

[Dobri]

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.

[sweety439]

For p == 3 mod 4, 2*p+1 (if it is prime) always divides 2^p-1 (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^p-1

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^p-1, you can also check that for which prime q, A001917(primepi(q)) is divisible by 3, 4, 5, 6, etc.

[kijinSeija]

Originally Posted by sweety439

For p == 3 mod 4, 2*p+1 (if it is prime) always divides 2^p-1 (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^p-1

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^p-1, you can also check that for which prime q, A001917(primepi(q)) is divisible by 3, 4, 5, 6, etc.

4p+1 never divides 2^p-1 right ? I can't find the sequences in OEIS

[sweety439]

Originally Posted by kijinSeija

4p+1 never divides 2^p-1 right ? I can't find the sequences in OEIS

Right, since 4p+1 is always == 5 mod 8, and for q == 5 mod 8, A001917(primepi(q)) is always odd and cannot be 4

[kijinSeija]

Originally Posted by sweety439

Right, since 4p+1 is always == 5 mod 8, and for q == 5 mod 8, A001917(primepi(q)) is always odd and cannot be 4

Thanks for your answer.

By the way, do you know the condition for example 6*p+1 or 10*p+1 divides 2^p-1 ?

I know the condition for 2*p+1 but I have no idea for these two for example.

[sweety439]

Originally Posted by kijinSeija

Thanks for your answer.

By the way, do you know the condition for example 6*p+1 or 10*p+1 divides 2^p-1 ?

I know the condition for 2*p+1 but I have no idea for these two for example.

No, I want to know how to compute A001917(q) for an odd prime q with given congruent class mod some numbers (say 8 or 24), I want to know the condition for A001917(q) is divisible by given number r, it is equivalent to 2 is r-th power residue (quadratic residue for r=2, cubic residue for r=3, quartic residue for r=4, etc., we should use cubic reciprocity and quartic reciprocity to solve, I do not think it can be solved for r>4 (except r=8 and r=16), since a general quintic equation cannot be solved algebraically) mod q (where r is the largest such number dividing q-1), such prime q must divide Phi((q-1)/r,2), where Phi is the cyclotomic polynomial, and (let p = (q-1)/r) if p is prime, then this is 2^p-1, if p is twice a prime, then this is the Wagstaff number (2^(p/2)+1)/3, and if p is power of 2, then this is the Fermat number 2^(p/2)+1

[charybdis]

Originally Posted by sweety439

I do not think it can be solved for r>4 (except r=8 and r=16), since a general quintic equation cannot be solved algebraically

Well you didn't think enough. This has absolutely nothing to do with the unsolvability of the general quintic.

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.