Between Fermat and Mersenne

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 2n−1, and a Fermat prime is one of the form 2n+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: 23+1 = 32.

But what I want is the following. For which positive integers n is it the case that each of 2n−1 and 2n+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,

211−1 = 23×89,   211+1 = 3×683.

As usual, thoughts welcome.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems and tagged , , . Bookmark the permalink.

15 Responses to Between Fermat and Mersenne

  1. 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 (On Toric Orbits in the Affine Sieve by Kontorovich and Lagarias)

  2. Kevin says:

    This paper appeared on the arXiv Monday:
    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.

  3. 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).

  4. Ofir G. says:

    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.

  5. Ofir G. says:

    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.

  6. Dima says:

    Ofir, for n=4 one has 2^n-1=3\times 5, 2^n+1=17, 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.

  7. Dima says:

    for 0<n<200, one has the following n for which both 2^n-1 and 2^n+1 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.

  8. Dima says:

    in the list above, 3 should be skipped, as 2^3+1 is a square.

  9. Dima says:

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

    There are also primes 313 and 701 there, s.t. (2^n+1)/3 is prime;
    however 2^313-1 has 4 prime factors, and 2^701-1 has 8 factors.

  10. Dima says:

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

  11. Dima says:

    by the way, n such that (2^n+1)/3 is a prime are called Wagstaff numbers, see e.g. and – seems to be quite a bit was done on these,

  12. Michel Marcus says:

    I guess you want OEIS A283364 ?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.