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?

  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Jan 26 '16 at 7:48
  • 3
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Jan 26 '16 at 7:57
  • $\begingroup$ mersenne.org/report_factors/… $\endgroup$ – Michael Stocker Jan 26 '16 at 9:08
  • $\begingroup$ It should not be hard to find even bigger mersenne numbers that are composite. $\endgroup$ – Michael Stocker Jan 26 '16 at 9:08
  • $\begingroup$ It is not known whether infinite many composite mersenne-numbers with prime exponent exist, although it is very likely that it is the case. $\endgroup$ – 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,

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

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

  • $\begingroup$ 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. $\endgroup$ – TonyK Jan 26 '16 at 18:22
  • $\begingroup$ "Of course there are" ? $\endgroup$ – Peter Jan 26 '16 at 19:34
  • $\begingroup$ @Peter: Yes, I know, I'm sticking my neck out. Next thing, I'll be claiming that $\pi+e$ is irrational. $\endgroup$ – TonyK Jan 27 '16 at 0:56
  • $\begingroup$ 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. $\endgroup$ – 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
? 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)))
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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.