# On prime numbers

let $q$ be a prime

let $p = 2^q -1$

is p must be prime always for any prime q ?

is this is true always ? or it is false for some prime q ?

if it is false , give an example to show that there is a prime q such that $2^q -1$ is not a prime

thanx

-
No, no, yes. $\,2^{67}-1\,$ is not a prime, and it is worwhile to read how result was presented. – DonAntonio Mar 14 '13 at 4:40
Of course, large Mersenne primes would be ridiculously easy to find if you could just take 2 to the last known Mersenne prime and subtract 1. – Waleed Khan Mar 14 '13 at 4:42
If such a formula existed (which generates a bigger prime from any known prime), then we could generate arbitrarily large prime numbers, and there would be no sense in searching for even bigger and bigger primes. – vsz Mar 14 '13 at 7:15

It is a theorem that if $p=2^q-1$ is prime then $q$ is necessarily prime. However, the converse is not true. One counterexample to the converse is: $2^{11}-1 = 89\times 23$.

-

Such primes $q$ seem to be in fact very rare. The first example is that $2^{11}-1$ is not prime. I leave it to you to find its non-trivial factors.

-

Such a number is called a Mersenne prime. In fact, we only know 48 such Mersenne primes, so most numbers in this form are not prime.

-
Question: if there are only 48, why are they worth studying? The prime numbers are distributed all over the place, might it not be that, really, pretty much any formula could be shown to be verified by a few dozen reasonably small primes? – Jack M Mar 14 '13 at 6:33
@JackM : there might be more than 48, we only know 48 of them. Actually, until a few weeks ago, we only knew 47. – vsz Mar 14 '13 at 7:13
It is apparently easier to test that a Mersenne number is prime than primes in general (which is a big deal with numbers this large). – Kathy Van Stone Mar 14 '13 at 16:37

Here's some example computations to suggest a way you might try to prove that $q$ must be prime:

$$x^2 - 1 = (x - 1)(x + 1)$$

So:

$$x^6 - 1 = (x^3)^2 - 1 = (x^3 - 1)(x^3 + 1)$$

And so:

$$2^6 - 1 = 63 = (2^3 - 1)(2^3 + 1) = 7 \cdot 9$$

Or:

$$x^3 - 1 = (x - 1)(x^2 + x + 1)$$

So:

$$x^{15} - 1 = (x^5)^3 - 1 = (x^5 - 1)(x^{10} + x^5 + 1)$$

And so:

$$2^{15} - 1 = 32767 = (2^5 - 1)(x^{10} + 2^5 + 1) = 31 \cdot 1057$$

-

$q=2^p-1$

$q$ is a $prime$. There its factors are $1$ and $q$.

$1.q=2^p-1$

If $p$ wasn't $prime$ and was of the form $a_1a_2a_3...a_n$,

$2^{a_1a_2...a_n}-1= (2^{a_2a_3...a_n})^{a_1}-1^{a_1}= A.B$

And $A,B \ge 2$

Which contradicts the fact that $q$ is prime. Therefore, $p$ has to be prime.

But when we take $p$ .

$2^p-1=(2-1)(2^{p-1}+2^{p-2}....1)$

Note that $(2^{p-1}+2^{p-2}....1)$ can/cannot be a $prime$.

-