Disproving the claim that the numbers 1+2+4, 1+2+4+8, 1+2+4+8+16... alternate between prime and composite

Question

I am working through an elementary number theory book and I have come across the following problem.

Show the following claims are wrong:

Claim 1: The sequence 1+2+4, 1+2+4+8, 1+2+4+8+16, ... is alternately prime and composite.

Claim 2: One or both of the numbers 6n-1 and 6n+1 are prime.

I have actually found counterexamples to both claims, but it was only through cold hard number-crunching. I want to believe this problem wouldn't be here unless there was supposed to be some elegant way to disprove these claims. Is there some other way to disprove the claims other than just finding a counterexample?

Note: the two claims are not meant to be related in any way.

Answer 1

Number crunching is a time-honored technique; many conjectures are far more easily solved by actually testing them (either in a brute-force fashion or by more clever searches) rather than thinking hard about them.

But sometimes these conjectures -- as well as the methods of disproving them -- suggest more general statements. The numbers in your first conjecture are

$$ \sum_{i=0}^{n-1} 2^i = 2^n - 1$$

are called Mersenne numbers. As you've noted, it's easy enough to prove they don't alternate prime/composite, and there are a number of theorems about when a Mersenne number can be prime or composite (e.g. for $2^n - 1$ to be prime, $n$ must also be prime)

There are also open questions -- e.g. nobody knows whether or not there are infinitely many Mersenne numbers that are prime.

Answer 2

For Claim 2: The numbers $m!+2, m!+3,\dots,m!+m$ will all be composite. If $m$ is large enough, this sequence will contain some $6n-1$ and $6n+1$.

For Claim 1: Note that $2^{ab}-1$ is always divisible by $2^a-1$ (since $x-1$ divides $x^b-1$ in $\Bbb{Z}[x]$, now let $x=2^a$); hence $2^8-1, 2^9-1, 2^{10}-1$ are all composite.

Answer 3

1. For $ n=6k+2 $ the numbers $ 2^n-1 $ and $ 2^{n+1}-1 $ are both composite.
2. For $ n= 6^{2k} $ the numbers $ 6n+1, 6n-1 $ are both composite.

Answer 4

A nice simple one for claim 2:

Note that both terms of the pair $(x^3+1, x^3-1)$ factorize (having simplest factors of $x+1$ and $x-1$ respectively), and that $(6n+1,6n-1)$ will be of that form if $n=6^2$.

(Which is just $(217,215)$, and indeed the pair are divisible by 7 and 5 respectively).

This argument extends to pairs of the form $(kn+1, kn-1)$ for $k>2$ (though the case for $k$ odd is obvious anyway, since both members will be even).

Answer 5

For the fun of it, I constructed the smallest counter-examples to both claims by hand (well, actually in my head). Here's the results, as well as how I went about finding them.

Claim 1: The seventh member of the series, $1+2+4+8+16+32+64+128+256=511$ is composite, not prime as specified. $511 = 7*73$.

This claim becomes easier to disprove once we recognize that the elements,

$7, 15, 31, 63, 127, 255, 511, ...$

are the Mersenne numbers, $2^n-1$, starting at $n = 3$. A useful fact about Mersenne numbers is that a Mersenne number can only be prime if its exponent, $n$, is prime. This immediately implies that elements $2, 4, 6, 7$ of the given series are composite. Thus we see that element $7$, $511$, must be a counter-example, because it is an composite odd-numbered element. To verify that it is the smallest counter-example, we need only verify that elements $1,3,5$, namely $7, 31, 127$ are prime. They indeed are, so $511$ is the smallest counter-example.

Claim 2: $n = 20, (119,121)$. $119 = 7*17, 121 = 11*11$

To find this, I categorized the possible solutions by the lower prime factor of $6n-1$ and $6n+1$. Clearly, neither value will be $2$ or $3$. First, I tried the pair $(5,7)$.

I calculated that $x \equiv 0 \mod 5$ and $x \equiv -1 \text{ or } 1 \mod 6$ implies $x \equiv 5\text{ or }25 \mod 30$ respectively, so the other member of the pair must equal $7\text{ or }23 \mod 30$. The smallest multiples of 7 satisfying those congruences, other than 7 itself, are $217$ and $203$, respectively.

Since I was not sure that this solution $(203, 205)$ was as small as possible, I repeated the process for the pair of factors $(5, 11)$. Reusing the congruence $7\text{ or }23 \mod 30$ for the multiple of $11$, I found the smallest multiples $187$ and $143$.

At this point, my smallest counter-example was $(143, 145)$. There only remained one case to check: $(119,121)$, because $121$ is the only number with $11$ as its smallest factor under $143$, and I had already checked that the pair $(5,7)$ had no solutions under $(143, 145)$. As it turns out, $(119,121)$ is a solution, so it must be the smallest.