TITLE: Large regions of the plane $(x,y) \in \mathbb{Z}^2$ with no relatively prime points: $\mathrm{gcd}(x,y) > 1$
QUESTION [3 upvotes]: 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$.

REPLY [4 votes]: Yes, this is possible.
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.
{"set_name": "stack_exchange", "score": 3, "question_id": 1410523}