10
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ You did it the sensible way. For the second, there would be fancier ways that appeal to the density of the primes. $\endgroup$ – André Nicolas Aug 20 '14 at 19:21
  • $\begingroup$ For the second, you could also use the Chinese Remainder Theorem. But that would be overkill, unless you are interested in generalizations. $\endgroup$ – André Nicolas Aug 20 '14 at 19:28
  • $\begingroup$ About the only clever thing available in the first one is finding good candidates. Note that this sequence can be written as $7,15,31,$etc i.e. $\{2^{n+2}-1\}$. We can then look for a counter-example by finding an odd $n=2k-1$ such that $2^{n+2}-1=2\cdot 4^{k}-1$ is composite. That eliminates a lot of the brute-force work immediately. $\endgroup$ – Semiclassical Aug 20 '14 at 19:29
  • 5
    $\begingroup$ Since the claims are totally unrelated, they should have been two separate questions. $\endgroup$ – user147263 Aug 20 '14 at 20:17
  • 3
    $\begingroup$ Perhaps, but since I solved them in a similar way and had a similar question for both, I opted for one question. $\endgroup$ – candido Aug 20 '14 at 20:32
18
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ A more concrete proof of 2 is to take $m=7$, so that you have 6 consecutive composite numbers. $\endgroup$ – Ian Aug 20 '14 at 21:15
  • $\begingroup$ $m!$ will be a multiple of 6 for any $m > 2$, so the composites you would be interested in are $m! + 5$ and $m! + 7$. Those will be composite if $m = 7$. Actually the only properties about $m!$ being used in the proof is that it is divisible by $5$, $6$, and $7$. So instead of $m!$ one could just use $5*6*7$, in which case $n$ ends up being $5*7+1$ $\endgroup$ – kasperd Aug 20 '14 at 22:25
8
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I believe you mean $\sum_{i=0}^{n-1} 2^i,$ not $\sum_{i = 0}^{n-1}2^n.$ $\endgroup$ – user71641 Aug 20 '14 at 21:05
  • $\begingroup$ @nsanger: Thanks, fixed. $\endgroup$ – Hurkyl Aug 20 '14 at 21:24
1
$\begingroup$
  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.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ Also, for $n=6^{6k-1}$, we have the factorizations $6n\pm1=6^{6k}\pm1=(6^{2k}\pm1)(6^{4k}\mp6^{2k}+1)$. $\endgroup$ – Barry Cipra Aug 20 '14 at 20:13
  • $\begingroup$ Yes, the statement is based on this equality $\endgroup$ – Yog Urt Aug 20 '14 at 20:22
  • $\begingroup$ I see that $6\pm1$ divides $6n\pm1$ when $n=6^{2k}$, but that's a little different from what I have in my comment (which in retrospect should have been done with an exponent $3k-1$ instead of $6k-1$). $\endgroup$ – Barry Cipra Aug 20 '14 at 20:35
  • $\begingroup$ Yes it is, thank you $\endgroup$ – Yog Urt Aug 20 '14 at 20:43
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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