# Occurence of numbers not divisible by primes

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.

• I could not exactly understand your question, can you please be a little more clear?
– Hawk
Mar 14, 2014 at 20:29
• @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$.
– user14972
Mar 14, 2014 at 20:34
• 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$. Mar 14, 2014 at 20:36
• 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. Mar 14, 2014 at 20:59
• 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}
– benh
Mar 14, 2014 at 23:05

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