1
$\begingroup$

I can prove the falsity by showing for $n=23$ there is no prime number between 23 and 23+6. But I am curious whether there is any other methods such as

  • proof by induction or
  • proof by contradiction

to prove it.

$\endgroup$
4
$\begingroup$

Yes. Let $\pi$ be the prime counting function $\pi(x)=\#\{p\text{ prime}\mid p\leqslant x\}$. If there was always a prime between $n$ and $n+6$, then, we would have $\frac{\pi(x)}x\geqslant\frac16$. But, in fact, $\lim_{x\to\infty}\frac{\pi(x)}x=0$ by the prime number theorem.

$\endgroup$
0
4
$\begingroup$

Well, since you are claiming that "a statement about all $n$" is false for some $n$, you won't be able to work by induction.

By contradiction: Assume there is always a prime number strictly between $n$ and $n+6$. Since $24, 25, 26, 27$ and $28$ are not primes, $29-23 < 6$, therefore $6 < 6$

But I think you can easily see that this is equivalent to the counterexample you posted

$\endgroup$
1
  • $\begingroup$ not quite true, you could start with a least example and induce via the primes a higher counter example. $\endgroup$ – user645636 Aug 2 '19 at 20:10
3
$\begingroup$

A mathematically simple approach that proves the existence of a run of composites (also called a prime gap) of any length:

Let $l$ be one more than the length of the gap you're looking for (in this case, $l = 6$).
Then consider $l!$ ($l$ factorial). By construction, $l!$ is a multiple of every natural number up to and including $l$. Then $l! + 2$ is a multiple of 2, because it's 2 more than a multiple of 2.
$l! + 3$ is a multiple of 3, because it's 3 more than a multiple of 3.
$...$
$l! + l$ is a multiple of $l$, because it's $l$ more than a multiple of $l$.

So for any given $l$, $l! + 2 \dots l! + l$ will be $l-1$ successive composite numbers. For $l=6$ we can see by inspection that this holds true for $722, 723, 724, 725, 726$ which are all composite.


A more ad-hoc approach which finds your example: Five natural numbers in a row must include three evens and two odds, or three odds and two evens, and the evens are certainly composite as long as they're greater than 2, so we only need to consider the odds. If we can find an odd $n$ such that $n$ and $n+2$ are both composite, that's enough for a contradiction.

If they exist, they must be divisible by distinct primes, since two multiples of 3 can't differ by 2, two multiples of 5 can't differ by 2, etc. Might as well start with the smallest odd primes available — if we can do it for 3 and 5 it will certainly happen by 15. Well, a quick inspection shows that 10 and 12 are a multiple of 5 and a multiple of 3 separated by 2, but they're even and we want odds, which is a sign that we should have been be working mod 30 the whole time. So we add 15 to come up with 25 and 27.

Now we see:

If $n \equiv 24 \pmod{30}$ then $n$ is composite (divisible by 2).
If $n \equiv 25 \pmod{30}$ then $n$ is composite (divisible by 5).
If $n \equiv 26 \pmod{30}$ then $n$ is composite (divisible by 2).
If $n \equiv 27 \pmod{30}$ then $n$ is composite (divisible by 3).
If $n \equiv 28 \pmod{30}$ then $n$ is composite (divisible by 2).

Still a little bit brute-force, but maybe it feels like has a little bit of a reason behind it. By considering the first three primes, 2, 3, and 5, we found the same run of 5 composites that you did, but also a proof that it repeats with a period of $2*3*5 = 30$. So 54, 55, 56 57, 58 are also all composite (and also surrounded by primes on both sides, but don't count on that happening forever — in the first step we proved that there must eventually be a gap of more than 30!)

$\endgroup$
4
  • $\begingroup$ Love your choice of the letter $l$. Wonderfully confusing! Mwahahahaha! $\endgroup$ – The Short One Jul 18 '19 at 21:33
  • $\begingroup$ Sorry, couldn't think of an appropriate one besides l for length. At least in math fonts it's not too confusable. :) $\endgroup$ – hobbs Jul 18 '19 at 21:34
  • $\begingroup$ I'm not complaining. But if anyone does complain, you could change it to $\mathcal L$. $\endgroup$ – The Short One Jul 18 '19 at 21:37
  • 1
    $\begingroup$ @TheShortOne: Nah, change it to "$\ell$" (\ell). $\endgroup$ – user21820 Sep 26 '19 at 10:01
1
$\begingroup$

Yeah, it's called the reverse of the distributive property of multiplication over addition/subtraction. (factoring out)

$$30=5\cdot 3\cdot 2$$

This, together with factoring out, show that adding or subtracting any multiple of 2,3 or 5 will be divisible by 2, 3 or 5, respectively. Since all numbers in 2,3,4,5, and 6 are divisible by 2,3 or 5 then the nearest possible primes around 30 are adding or subtracting 1 or adding or subtracting 7. This then shows a minimum gap of 6 in between 2 potential primes that aren't twins around 30. Applying this to: $$210=7\cdot 5\cdot 3\cdot 2$$ we get a gap forced to 10 or more.

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