Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
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

5 Answers 5

up vote 5 down vote accepted

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$.

share|improve this answer

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.

You may want to read about Mersenne primes.

share|improve this answer

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.

share|improve this answer
    
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$$

share|improve this answer

$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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.