6
$\begingroup$

Consider a prime number $q$. Is it true that every sequence of q consecutive integers contains at least one integer not divisible by any prime $p, p < q$? It seems to be so in any specific instance I look at, but I don't know how to prove it as a general statement.

$\endgroup$
  • $\begingroup$ I could not exactly understand your question, can you please be a little more clear? $\endgroup$ – Hawk Mar 14 '14 at 20:29
  • $\begingroup$ @Hawk: He's asking if there must be an $x$ in the interval that has no divisors smaller than $q$; i.e. that $\gcd(x, (q-1)!) = 1$. $\endgroup$ – Hurkyl Mar 14 '14 at 20:34
  • $\begingroup$ In other words, in every sequence of q consecutive integers, there is at least one integer $b$ such that $b(mod p)$ is not zero for every $p < q$. $\endgroup$ – Keith Backman Mar 14 '14 at 20:36
  • $\begingroup$ It might help to realize that if one considers the specific interval $q$+1 to 2$q$, my question is equivalent to Bertrand's Postulate. But it seems to me to be true for all sequences of q consecutive integers. $\endgroup$ – Keith Backman Mar 14 '14 at 20:59
  • 2
    $\begingroup$ It can be proven for $q\leq 11$, but for $q\geq 13$ I think there are the following counter-examples ($q$ : first number in the sequence of $q$ consecutive): \begin{eqnarray} 13&:& 114\\ 17&:& 2184 \\ 19&:&9440 \\ 23&:&1334 \\ 29&:&60044 \\ 31&:&60044 \\ 37&:&2734892 \end{eqnarray} $\endgroup$ – benh Mar 14 '14 at 23:05
2
$\begingroup$

No. Here's a disproof that works for all $q\ge 13$.

Label the primes $p_1<p_2<\cdots <p_{n+1}=q$.

First some motivation. A fairly long sequence of consecutive numbers, each divisible by some prime $<q$ is $q!+2,\ldots, q!+q-1$, but this isn't quite long enough. We also have the sequence $q!-q+1,\ldots, q!-2$ on the other side. If there was only a way to connect up these two!

Sure, if we knocked some primes off of $q!$.

Let $P=cp_1\cdots p_{n-2}$. Choose $c$ such that $p_{n-1}\mid P-1$ and $p_{n}\mid P+1$, possible by the Chinese remainder theorem. Now $P-p_{n-1}+1,\ldots, P-2$ and $P+2,\ldots, P-p_{n-1}-1$ are each divisible by some prime in $p_1,\ldots, p_{n-2}$. We obtain a sequence of $2p_{n-1}-1$ consecutive integers each divisible by some prime in $p_1,\ldots, p_n$. It suffices that $\boxed{2p_{n-1}-1\ge p_{n+1}=q}$, which happens for $q\ge 13$.

$\endgroup$
  • $\begingroup$ Many thanks to benh and Holden Lee. I note that although Lee's proof is enlightening about benh's example for 13, I do not find it illuminating for the other examples. It seems to be the case that the proof establishes that such counterexamples exist, but does not necessarily point to the smallest occurrence of them. @benh -- did you find your examples using an algorithm that is other than a brute force search? $\endgroup$ – Keith Backman Mar 20 '14 at 16:00
  • $\begingroup$ Perhaps there is a better general construction, but I doubt there's any explicit expression for the smallest counterexample in general. $\endgroup$ – Holden Lee Mar 20 '14 at 21:20

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.