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.

In 1556, Tartaglia claimed that the sums
1 + 2 + 4
1 + 2 + 4 + 8
1 + 2 + 4 + 8 + 16
are alternative prime and composite. Show that his conjecture is false.

With a simple counter example, $1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255$, apparently it's false. However, I want to prove it in general case instead of using a specific counter example, but I got stuck :( ! I tried:
The sum $\sum_{i=0}^n 2^i$ is equal to $2^{n+1} - 1$. I assumed that $2^{n+1} - 1$ is prime, then we must show that $2^{n+1} - 1 + 2^{n+1} = 2^{n+2} - 1$ is not composite. Or we assume $2^{n+1}$ is composite and we must show that $2^{n+2} - 1$ is not prime. But I have no clue how $2^{n+2} - 1$ relates to its previous prime/composite. Any hint?

share|improve this question
4  
I don't seem to understand your question. If you want to prove something is false, all you need is one counter example. Anyway some facts about numbers of the form $2^n - 1$. If this number is prime, the $n$ is a prime. or to put it the other way, if $n$ is composite, then $2^n - 1$ is composite. –  user17762 Feb 2 '11 at 6:00
1  
Sivaram is correct. You only need one counterexample to disprove a "for all" claim. So 255=3x5x17 and 511=7x73, both composite, are sufficient to disprove the claim. In this case, you can say more, as my answer shows. –  Ross Millikan Feb 2 '11 at 6:09
    
If $n > 2$ and $2^n-1$ is prime then $2^{n+1}-1$ is composite (see Ross's proof). If $2^n-1$ is composite then either $2^{n+1}-1$ is prime or not, for example $2^4-1=15$ is composite and $2^5-1=31$ is prime, $2^8-1=255$ is composite and so is $2^9-1=511$. –  Yuval Filmus Feb 2 '11 at 6:10
    
Sorry guys, I just want to learn something new. –  Chan Feb 2 '11 at 6:11
    
Note also that p being prime is necessary but not sufficient for 2^p-1 to be prime as 2^11-1=2047=23*89 shows. –  Ross Millikan Feb 2 '11 at 15:25
show 2 more comments

5 Answers

up vote 12 down vote accepted

It is known that $2^n-1$ can only be prime if $n$ is prime. This is because if $jk=n$, $2^n-1=\sum_{i=0}^{n-1}2^i=\sum_{i=0}^{j-1} 2^i \sum_{i=0}^{k-1} 2^{ij}$ So they will only continue to alternate at twin primes. In particular, $2^{6k+2}-1, 2^{6k+3}-1$ and $2^{6k+4}-1$ will all be composite

share|improve this answer
    
succinct and cute proof! Great thanks ;) –  Chan Feb 2 '11 at 6:07
add comment

There is simply no such correlation in general. If that were the case, Mersenne primes would not be as interesting to study as they are. You can not prove that $2^n-1$ composite $\Rightarrow 2^{n+1} - 1$ prime, because it isn't true. As Ross mentioned, $2^n-1$ can only be prime when $n$ is prime, so for any prime $p > 2$, if $2^p-1$ is prime, then $2^{p+1}-1$ must be composite, as $2 \mid (p+1)$.

share|improve this answer
add comment

Although Ross's proof is much shorter and elegant I show my exercising because it uses a slightly different logic.

Assume, at some n we have $\small 2^n-1 = p_0 $ where $\small p_0 $ is prime. We use only the fact, that n must then be odd (otherwise it would factor into $\small (2^{n/2}-1)(2^{n/2}+1) $), so we write explicitely $\small n=2m + 1$.

With this Tartaglia's claim means, that

  1. $\small 2^{2m+1} -1 =p_0 \in \mathbb P $ (we observe that this is true for instance for m=1, so: $\small 2^3-1 = 7 \in \mathbb P $ )

  2. $\small 2^{2m+1+2k} -1 =p_k \in \mathbb P $ for all positive integer k


To arrive at a contradiction we rewrite the expressions

$\small \begin{array} {rclllllll} 2^{2m+1} &=& p_0+1 \\ 2^{2m+1+2k} &=& p_k+1 & =& 2^{2m+1}*4^k &=& 4^k(p_0+1) \\ &\to& \\ p_k&=&4^k p_0 + 4^k-1 \end{array} $

The little fermat says, that for each odd prime p there is some k such that $\small 4^k-1 $ is divisible by p namely $\small k=p-1 $ so we'lll have $\small 4^{p_0-1}-1 = p_0 \cdot x $ where x is some positive integer. From this follows that there is some k such that $\small p_k \notin \mathbb P $:

$ \small p_{p_0-1} = 4^{p_0-1} p_0 + 4^{p_0-1}-1 =4^{p_0-1} p_0 + p_0 \cdot x = p_0 \cdot (4^{p_0-1} + x ) \notin \mathbb P $

share|improve this answer
add comment

If $2^{n}-1$ is prime, then $n$ must be odd, otherwise, we could factor $2^{n}-1$ as $(2^{n/2}+1)(2^{n/2}-1).$

So at least every other number in the series $2^n-1,n=1,2,3...$ must be composite, by the conjugacy rule.

EDIT: Reread the question, but you can do the same for $a^3-b^3 = (a-b)(a^2+ab+b^2)$ so whenever $n$ is divisible by 3, you can do a factorization as above. In general, $a^n-b^n$ is divisible by $a-b,$ so if $n$ is not prime, $n=pq$, and we have $$2^{n}-1 = (2^q)^p - 1^p = (2^q-1)Q$$ where $Q$ is an integer.

share|improve this answer
add comment

It is easy to see that $2^{2n}-1 \equiv 0 \mod 3$. This shows that for $n \geq 2$, $2^{2n}-1$ is never prime.

Also, since $2^3 \equiv 1 \mod 7$ it follows that $2^{3n} -1$ is always divisible by $7$.

Hence $2^{6n+2}-1, 2^{6n+3}-1, 2^{6n+4}-1$ are always composite.

share|improve this answer
add comment

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.