# Largest Mersenne composites with prime exponent?

I understand that it is an open problem whether there are an infinite number of composite numbers of the form $2^p-1$ with $p$ prime.

Is it possible to find examples of such numbers that are much larger than the largest known Mersenne prime? What is the largest known? I was thinking that short of solving the open problem I could try to show that $2^{n^2+1}-1$ is prime for only finitely many $n$, since it is also unknown if there are infinitely many $n$ with $n^2+1$ prime. Is there any conjecturally infinite set of primes that is easily computable for which $2^p-1$ is always composite?

• Interesting question. I only have a useless comment. We get composites with primes $p$ such that $2p+1$ is prime. The known Sophie Germain primes do not extend very far, but the existence of infinitely many is tied to a number of other number-theoretic conjectures. – André Nicolas Jan 26 '16 at 7:48
• Correction, we need the Sophie Germain prime to be congruent to $3$ modulo $4$ for the proof to go through. This is because the argument uses the fact that $2$ is a quadratic residue of $2p+1$. – André Nicolas Jan 26 '16 at 7:57
• mersenne.org/report_factors/… – Michael Stocker Jan 26 '16 at 9:08
• It should not be hard to find even bigger mersenne numbers that are composite. – Michael Stocker Jan 26 '16 at 9:08
• It is not known whether infinite many composite mersenne-numbers with prime exponent exist, although it is very likely that it is the case. – Peter Jan 26 '16 at 17:58

It is easy to find composite mersenne numbers. With trial division I found in only a couple of minutes that

p = 100.000.223, 200.000.039, 400.000.043, 800.000.171, 1.600.000.091, 2.000.000.279

satisfy $2p+1 | 2^p-1$.

Unfortunatly javas BigInteger doesn't support much bigger Integers, so I had stopped there.

• The point is, nobody has ever managed to prove that there are an infinite number of these composite Mersenne numbers. Of course there are; but proving it is another matter. – TonyK Jan 26 '16 at 18:22
• "Of course there are" ? – Peter Jan 26 '16 at 19:34
• @Peter: Yes, I know, I'm sticking my neck out. Next thing, I'll be claiming that $\pi+e$ is irrational. – TonyK Jan 27 '16 at 0:56
• You can do it in PARI/GP with isExample(p)=Mod(2,2*p+1)^p-1==0 && isprime(p). If you use forprime function to test all primes greater than some arbitrary value, you can quickly find examples like 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009223 ($10^{100}+9223$). Related to early comments to the question above by André Nicolas, and related to OEIS A002515. – Jeppe Stig Nielsen Mar 28 '17 at 23:56

Using the self-programmed powmod-function in PARI/GP, I got :

? powmod
%50 = (b,n)->w=binary(b);x=2;for(j=2,length(w),x=x^2;if(w[j]==1,x=x*2);    x=compone
nt(Mod(x,n),2));x
? p=10^10;gefunden=0;while(gefunden==0,p=nextprime(p+1);print(p);v=0;q=1;  gef=0;w
hile((gef==0)*(v<1000),v=v+1;q=q+2*p;while(isprime(q)==0,q=q+2*p);  if(powmod(p,q)
==1,gef=1));if(powmod(p,q)==1,gefunden=1;print(p,"  ",q)))
10000000019
10000000033
10000000061
10000000069
10000000097
10000000103
10000000121
10000000141
10000000147
10000000207
10000000259
10000000277
10000000277  380000010527


That means $380,000,010,527|2^{10,000,000,277}-1$

Even larger examples :

100000000019  2263400000430047
1000000000169  608000000102753
1000000000000037  870000000000032191
100000000000000000151  2600000000000000003927