Mersenne Prime - why are these two definitions equivalent?

Question

According to Wikipedia:

If $n$ is a composite number then so is $2^n − 1$. ($2^{ab} − 1$ is divisible by both $2^a − 1$ and $2^b − 1$.) This definition is therefore equivalent to a definition as a prime number of the form $M_p = 2^p − 1$ for some prime $p$.

I'm wondering why the definition is equivalent. If $p$ is prime, it doesn't necessarily mean that $2^p-1$ is prime, of course. It does, however, mean from my understanding that by the contrapositive, if $2^n-1$ is prime, then $n$ is prime, but that doesn't help much. So what precisely does the second sentence mean?

Answer 1

It is not clear from your extract which definitions are being counted as equivalent. It looks like:

A Mersenne Prime is a prime of the form $2^n-1$

and

A Mersenne Prime is a prime of the form $2^p-1$ with $p$ prime

And the fact that if $n$ is composite, so is $2^n-1$ means that these define the same set of primes.

Answer 2

As stated, a Mersenne prime is a Mersenne number, i.e., a number of the form $$M_n=2^n-1$$ which is itself prime. Thus, in order for $M_n$ to be prime, $n$ must also be prime. This follows, as for any composite $n$ with factors $a$ and $b$, $n=ab$.

Thus $2^n-1$ can be written as $2^{ab}-1$, which is a binomial number that always has a factor $(2^a-1)$.

Answer 3

I think the paragraph is trying to say the following for $M_n$

$$ n \textrm{ composite} \Rightarrow M_n \textrm{ composite} $$ is equivalent to $$ M_n \neg \textrm{ composite} \Rightarrow n \neg \textrm{ composite} $$ I.e. is equivalent to $$ M_n \textrm{ prime} \Rightarrow n \textrm{ prime} $$

Answer 4

The claim is that the following two are equivalent for each $N$:

1. $N$ is a prime and $N$ can be written as $N=2^n-1$ where $n$ is a natural number.
2. $N$ is a prime and $N$ can be written as $N=2^p-1$ where $p$ is a prime.

Further, they say that because they are equivalent, both can be used as the definition of a Mersenne prime.

Proof that they are equivalent:

• Proof that 2 implies 1: Assume 2 is true. Just set $n=p$ in 1. Done.
• Proof that 1 implies 2: Assume 1 is true. $N=2^n-1$ is a prime, so $n$ can't be composite (as shown in your quote). So $n$ is a prime. So $N$ can be written as $2^p-1$ where $p$ is a prime. So 2 is true.