The following problem came up in something I was doing recently. I have no idea how difficult it is – it looks hard to me – but I would be glad to hear from anyone who knows more than I do.

As is well known, a Mersenne prime is one of the form 2^{n}−1, and a Fermat prime is one of the form 2^{n}+1. In each case, only finitely many examples are known, but it is thought that there may be infinitely many Mersenne primes but only finitely many Fermat primes.

If we relax “prime” to “prime power”, we get Catalan’s equation, which only gives us one new solution: 2^{3}+1 = 3^{2}.

But what I want is the following. For which positive integers *n* is it the case that each of 2^{n}−1 and 2^{n}+1 is the product of at most two distinct primes?

It happens that, in many small cases, if one of these numbers is prime, the other is a product of two primes; but this may be just the law of small numbers. But there are other cases. For example,

2^{11}−1 = 23×89, 2^{11}+1 = 3×683.

As usual, thoughts welcome.

### Like this:

Like Loading...

*Related*

##
About Peter Cameron

I count all the things that need to be counted.

I believe the heuristic for these types of problems is that there will only be a finite number of n for which 2^n+1 and 2^n-1 are both a product of at most two primes. Some discussion on conjectures and heuristics for these types of problems is contained in https://arxiv.org/abs/1808.03235 (On Toric Orbits in the Affine Sieve by Kontorovich and Lagarias)

This paper appeared on the arXiv Monday: https://arxiv.org/abs/2010.01789

Based on the abstract, it is not exactly what you are looking for, but certainly it is related. Maybe it would be useful in a variant of the problem you are studying.

Thanks, Peter and Kevin. I also would guess that there are only finitely many solutions, but juding by the evidence it will not be a short list.

Note that n is odd, so 2n+1 is divisible by 3; so a necessary condition is that (2n+1)/3 is prime. The other part is not so straightforward.

As a footnote, these are precisely the values of n for which the power graph of PSL(2,2n) is a threshold graph (if you know about such things).

Sorry, the new WordPress editor killed my superscripts: all n’s above should be superscripts.

Sorry, another small correction. These graphs are not threshold but they are cographs (for q satisfying this condition.

I stand corrected about my statement about 2^n+1: the condition is that 2*n is either an odd prime times a power of 2, or 3 times a power of 2.

So n *must* be a prime in order for both 2^n+1 and 2^n-1 to be products of at most two distinct primes.

Oops, it seems I didn’t submit my first comment…

Anyway, here are three observations that together prove that n must be a prime for both 2^n-1 and 2^n+1 to be prime or a product of two distinct primes:

1. 2^m-1 is divisible by 2^k-1 whenever k divides m.

2. 2^m+1 = (2^(2m)-1)/(2^m -1).

3. Bang’s Theorem states that for any m (other than 1 or 6), 2^m-1 has a prime factor not dividing 2^k-1 for all k<m.

Ofir, for n=4 one has 2^n-1=3\times 5, , so your argument is not water-tight.

If n=2m then 2^n-1=(2^m-1)(2^m+1), and the factors are both prime only if n=4. This doesn’t affect whether or not there are infinitely many.

If n has odd prime divisors p and q then 2^p-1 and 2^q-1 both divide 2^n-1 and their product is smaller than 2^n-1 so there cannot be only two prime factors.

for 0<n<200, one has the following n for which both and have at most 2 factors:

[1, 2, 3, 4, 5, 7, 11, 13, 17, 19, 23, 31, 61, 101, 127, 167, 199]

indeed, only non-prime n is 4 here. But the list isn't very sparse.

in the list above, 3 should be skipped, as is a square.

I’ve let the computer run a bit more, only checking primes 1000>n>2 such that is a prime (which is a necessary condition, as is divisible by 3), and found one more, n=347, which satisfies your condtions.

There are also primes 313 and 701 there, s.t. is prime;

however has 4 prime factors, and has 8 factors.

these non-editable and non-previewable comments, sorry 🙂 missed {}, twice, above

by the way, such that is a prime are called Wagstaff numbers, see e.g. https://en.wikipedia.org/wiki/Wagstaff_prime and https://oeis.org/A000978 – seems to be quite a bit was done on these,

I guess you want OEIS A283364 ?