Divisibility of numbers in intervals of the form $[kn,(k+1)n]$ [duplicate]

Question

I have checked that the following conjecture seems to be true:

There exists no interval of the form $[kn, (k+1)n]$ where each of the integers of the interval is divisible by at least one of the integers of the interval $(1,n]$

Note that the statement is easily provable for some intervals. For every $n$ and $k=0$ is true, as $1$ is not divisible by any of the integers of the interval $(1,n]$. For every $n$ and $k=(n-1)!$ is also true, as $n!+1$ is not divisible by any of the integers of the interval $(1,n]$.

Note also that there are $n-1$ integers in the interval $(1,n]$ and $n+1$ integers in the interval $[kn, (k+1)n]$, so by the Pigeonhole Principle, apart from $kn$ and $(k+1)n$, which are both divisible by $n$, there are at least another two integers of the interval divisible by the same integer of the interval $(1,n]$.

I guess that there is some modular relation supporting the statement. However, I am unable to prove it generally. Any hint towards a proof / disproof would be welcomed.

Thanks!

Answer 1

There exists no interval of the form $[kn,(k+1)n]$ where each of the integers of the interval is divisible by at least one of the integers of the interval $(1,n]$

To see why we might think this is true, let's try to construct a counterexample for $n=3$. The numbers in the interval are $3k,3k+1,3k+2,3k+3$, and each of these has to be divisible by either $2$ or $3$. But neither $3k+1$ nor $3k+2$ is divisible by $3$, and as consecutive integers, can't both be even. So the statement holds for $n=3$.

The first few $n$ are similar; however, for $n=8$, we can assign potential divisors to each number in the list:

Number	Divisor
$8k$	$2$
$8k+1$	$3$
$8k+2$	$2$
$8k+3$	$5$
$8k+4$	$2$
$8k+5$	$7$
$8k+6$	$2$
$8k+7$	$3$
$8k+8$	$2$

For the even numbers, this trivially holds. For the others, we can write the following congruences:

\begin{align} 8k+1 & \equiv 0\pmod{3} \\ 8k+3 & \equiv 0\pmod{5} \\ 8k+5 & \equiv 0\pmod{7} \end{align}

which become

\begin{align} k & \equiv 1\pmod{3} \\ k & \equiv 4\pmod{5} \\ k & \equiv 2\pmod{7} \end{align}

These have a solution by the Chinese Remainder Theorem; the smallest positive solution is $k=79$, giving the interval $[632,640]$ which is indeed a counterexample.