3
$\begingroup$

The Mersenne numbers (those numbers of the form $2^N-1$), like any positive integers greater than 1, may be either prime (having no divisors1 other than 1), or composite (able to be produced by the multiplication of two or more2 prime numbers). Prime Mersenne numbers, known as (what else) Mersenne primes, are interesting for a number of reasons, such as their use in generating extremely large perfect numbers3 and the tendency for the largest known prime at any given moment to be a Mersenne prime4 (a product of the unusual ease of primality-testing Mersenne numbers relative to other numbers of comparable size, as well as, in recent years, the wide availability of home computing software dedicated to this purpose).

Despite the rarity of Mersenne primes (only 51 are known as of 28 June 2021), they are still far more common than they should be:

The evidence at hand suggests that a randomly selected Mersenne number is much more likely to be prime than an arbitrary randomly selected odd integer of similar size.[3] [Wikipedia, "Mersenne prime", section "About Mersenne primes".]

Additionally, even the composite Mersenne numbers tend to be only poorly so, having relatively few and large factors. For instance, the smallest factor of M99346201, according to my copy of Prime95, is 26964590038118087464506577, or nearly 27 septillion. And this is at the low end of Mersenne-number factor sizes; only about one in ten Mersenne numbers has any factors small enough to be found by direct methods in a reasonable amount of time, even with modern computing power.

Why are Mersenne numbers so lacking in factors relative to other odd integers of comparable size?


1: Factors smaller than the number being factored.

2: "Two or more" here referring to the total number of terms in the fully-expanded prime factorisation of the number in question, rather than to the number of distinct prime factors of same.

3: Integers equal to the sum of their divisors (both prime and composite).

4: This has been the case from 30 January 1952 (when M521 was proven prime, followed within a few hours by M607) through to the present day, except for a brief gap from 6 August 1989 (when the non-Mersenne number $391581(2^{216193})-1$ was proven prime, narrowly outstripping M216091, the then-record-holder) through 17 February 1992 (when M756839 was proven prime).

$\endgroup$
1
  • 4
    $\begingroup$ if $p|2^q-1$, then $p=2kq+1$ $\endgroup$ Jul 2, 2021 at 0:50

2 Answers 2

1
$\begingroup$

To expand J. W. Tanner's answer:
An arbitrary prime p needs not to be divisible by any other prime below $\sqrt p$.
In case of Mersenne numbers, the smallest prime which can divide $2^p-1$ is $2p+1$. In addition, any divisor $q$ of $2^p-1$ is expressible as $q=2kp+1$ for some natural $k$. Also, $p\equiv\pm 1\mod 8$. The possible divisor $q$ also needs to be a prime, which happens rarely (like 90% of generated through $2kp+1$ integers are not primes).
It shows that Mersenne numbers have less divisors and are more likely to be prime than arbitrary number of the same size.

$\endgroup$
-1
$\begingroup$

One trick for producing prime numbers is to take a number with lots of factors and then add or subtract $1$. Then at least none of the factors of the original number will divide the new one, so a lot of possibilities are eliminated. So mathematicians have considered

$$2^n-1$$

$$2^n+1$$

$$n!+1$$

$$n!-1$$

and so on.

$\endgroup$
6
  • 3
    $\begingroup$ So $2^n$ has many prime factors does it ? $\endgroup$ Jul 2, 2021 at 22:13
  • 1
    $\begingroup$ @RoddyMacPhee I didn't say it did. $\endgroup$
    – B. Goddard
    Jul 2, 2021 at 22:15
  • 3
    $\begingroup$ You implied it, on a question about the form $2^n-1$, you're stating that it's more likely to be interesting and factor poor due to $2^n$ having many prime factors ... $\endgroup$ Jul 2, 2021 at 23:08
  • 2
    $\begingroup$ @RoddyMacPhee No I didn't. I didn't say it. I didn't imply it. $\endgroup$
    – B. Goddard
    Jul 3, 2021 at 0:42
  • $\begingroup$ Prime factors are the ones we need to care about ... $\endgroup$ Jul 3, 2021 at 10:34

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.