# Large regions of the plane $(x,y) \in \mathbb{Z}^2$ with no relatively prime points: $\mathrm{gcd}(x,y) > 1$

For any $\ell > 0$ can you find $M, N$ such that $\boxed{\mathrm{gcd}(x,y) > 1}$ for all $x \in [M, M+\ell]$ and all $y \in [N, N+\ell]$ ?

This is related to the statement that the set of integers $(x,y)$ such that $x, y$ are relatively prime has natural density $\frac{6}{\pi^2} \approx \frac{2}{3}$. I always read there are arbitrarily large patches in the plane with numbers that are not relatively prime.

This is kind of like finding long strings of consecutive composite numbers. The usual answer is $N! + k$ with $0 \leq k \leq N$.

• About your last assert: it is for $2\le k\le N$, since $N!+1$ can be prime. Commented Aug 26, 2015 at 17:39

Choose $(\ell+1)^2$ distinct prime numbers $$p_{i,j},\quad 0\leq i\leq\ell,\quad 0\leq j\leq\ell.$$ We might imagine that these are entries of a square matrix and form their row-wise and column-wise products as follows: $$q_i=\prod_{j=0}^\ell p_{i,j}\qquad\text{and}\qquad q^j=\prod_{i=0}^\ell p_{i,j}.$$ By construction the numbers $q_0,\ldots,q_\ell$ are pairwise coprime. The same holds for $q^0,\ldots,q^\ell$. Therefore, by the Chinese remainder theorem, the two systems of congruences $$x\equiv -i\pmod{q_i},\qquad 0\leq i\leq\ell,$$ and $$y\equiv -j\pmod{q^j},\qquad 0\leq j\leq\ell,$$ admit solutions $x$ and $y$. By construction, $x+i$ is divisible by $q_i$ and $y+j$ by $q^j$. Since $q_i$ and $q^j$ are both divisible by $p_{i,j}$ this means that $$\gcd(x+i,y+j)\geq p_{i,j}$$ completing the construction.
• @johnmangual: The point is that e.g. choosing $p_{i,j}=3$ for all $i,j$ doesn't work, because the $q_i$ will not be coprime anymore, violating the assumptions of the Chinese remainder theorem. Commented Aug 26, 2015 at 18:24