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

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

1 Answer 1


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.

  • $\begingroup$ What do you mean pairwise distinct? We have infinitely many prime numbers, so it's good. I am guessing you mean distinct along each row or each column ? $\endgroup$
    – cactus314
    Commented Aug 26, 2015 at 18:22
  • $\begingroup$ @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. $\endgroup$
    – Dejan Govc
    Commented Aug 26, 2015 at 18:24
  • $\begingroup$ this is perfect. the number you get using Chinese Remainder Theorem get pretty large, but all I asked is some way to assure me the existence of large holes. $\endgroup$
    – cactus314
    Commented Aug 26, 2015 at 18:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .