On the minimum integer not coprime to numbers in an interval Consider the set of positive integers $[a,a+1,\ldots, a+k]$ (i.e. the interval $[a,a+k]$). What can we say about the smallest positive integer $N$ such that $\gcd(a+i,N)>1$ for all $0\leq i\leq k$?
Can we prove that it is at least of order $k^4$ (and it would be great if we can give as explicit constants as possible)?
 A: The obvious interpretation of this question is to find the a bound for the smallest $N$ as $a \ge 2$ varies. For convenience, consider the interval $[a,a+X-1]$ of length exactly $X$. I will prove that  the smallest $N$ certainly grows faster than any power of $X$.
It's not hard to make the estimates in this answer perfectly explicit, but it would become a real mess, and unless one is very careful and works
extra you will end up having to assume that $X$ is very large and or consider many cases explicitly. The answer, however, can certainly be made explicit if desired.
Certainly we may take the smallest $N$ to be squarefree. Let us suppose that  $N = \prod_{i=1}^{n} q_i$ for distinct primes $q_i$.
Case 1 The number of primes factors is at least $n \ge \log X$. In this case, $N$ is at least the product of the first $n$ primes,
and thus the product of the primes $p \le p_n > n \log n \ge X \log X$. Since
$$\sum_{p \le Y} \log p \sim Y,$$
this implies that
$$N \ge  \exp(\log X \log \log X (1 - o(1))) = X^{\log \log X(1 - o(1))},$$
which shows that $N$ is (eventually) bigger than any power of $X$.
Case 2 The number $n$ of prime factors is bounded by $\log X$.
In this case we show that $N$ will be co-prime to at least one element in the interval for $X$ large enough. Let $f(d)$ denote the number of integers in the interval $[a,a+X-1]$ which have a factor in common with $d$. Then since every $d$th integer is divisible by $d$, we get
$$ \left| f(d) - \frac{X}{d} \right| \le 1.$$
By inclusion-exclusion, we deduce that the number of integers in $[a,a+X-1]$ which are prime to $N$ is equal to:
$$f(1) - \sum f(q_i) + \sum f(q_i q_j) - \ldots $$
We want to show that this is non-zero unless $N$ is large.
There are $2^n$ terms in this sum.
The "main term" gives
$$M =  X \prod \left(1 - \frac{1}{q_i} \right)$$
and the error term is bounded by $2^n$, because the error in each term is bounded by $1$. We can estimate the error term as
$$2^n \le 2^{\log X} = X^{\log 2} = X^{0.69\ldots}$$
Now let's estimate  $M$. It suffices to show that $M$ is bigger than the error term. We have $\log(1-x) \sim -x$.
$$\log M = \log X + \sum \log(1 - 1/q_i) \sim \log X  - \sum \frac{1}{q_i},$$
On the other hand, if we denote the primes in order by $p_1, p_2, p_3, \ldots$, then
$$ \sum_{i=1}^{n} \frac{1}{q_i} \le  \sum_{i=1}^{n} \frac{1}{p_i}.$$
By Merten's theorem, we have the  estimate
$$\sum_{p \le Y} \frac{1}{p} \sim \log \log Y.$$
If $Y = p_n$ is the $n$th prime and $n \le \log X$, then we can take $Y \sim X \log X$, and then
$$\log \log Y = \log \log (X \log X) \sim \log \log X \ll \log X,$$
and hence $\log M \sim \log X$ and so $M > X^{1 - o(1)} > X^{\log 2}$.
