23
$\begingroup$

After reading this question, I conjectured a generalization of it.

Conjecture: Fix $k\in \mathbb N$. Then, for all $n\in \mathbb N$, one of $n+1,\ldots,n+k$ is coprime to the rest.

I tried some elementary ways, but wasn't successful.

Observation: One of the consequences of this conjecture is that there are infinitely many primes!

$\endgroup$
  • $\begingroup$ I assume you meant k>1. Answer below is surprising to me. $\endgroup$ – DanielWainfleet Mar 30 '16 at 18:29
  • 3
    $\begingroup$ @user254665 If k=1, $n+1$ is coprime to all members of $\varnothing$ ! $\endgroup$ – user217174 Mar 30 '16 at 18:36
  • $\begingroup$ You got me on that one.:). $\endgroup$ – DanielWainfleet Mar 31 '16 at 1:53
34
$\begingroup$

Surprisingly, the statement is false once $k\ge17$, and the shortest counterexample is the sequence of length $17$ beginning with $2184$. This was the result of a line of work beginning with Pillai, and finally wrapped up by Brauer. See S.S. Pillai on Consecutive integers research paper?.

  • Pillai showed that it holds for $k<17$, but can fail for all $k$ between $17$ and $430$ - infinitely often, in fact!

  • In a sequence of results, this was improved until eventually Scott showed that there are infinitely many counterexamples for $17\le k\le 2491906561$ . . .

  • . . . and then Brauer showed that there are infinitely many counterexamples for any $k\ge 17$.

$\endgroup$
  • 1
    $\begingroup$ Thanks, it's amazing! Because I thought this conjecture is trivially true! $\endgroup$ – user217174 Mar 30 '16 at 16:08
  • 2
    $\begingroup$ oeis.org/A090318/internal $\endgroup$ – user217174 Mar 30 '16 at 16:14
  • 1
    $\begingroup$ I posted this observation at Examples of eventual counterexamples in MO. $\endgroup$ – user217174 Mar 30 '16 at 17:00
  • 1
    $\begingroup$ I would have expected a short elementary decision. Number theory is full of deceptively simple-sounding hard Q's. $\endgroup$ – DanielWainfleet Mar 30 '16 at 18:33

Your Answer

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