# If $2^{n+1} - 1$ is composite, is $2^{n+2} - 1$ prime?

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?

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

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

-
succinct and cute proof! Great thanks ;) –  Chan Feb 2 '11 at 6:07

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

-

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$

-

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.

-

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.

-