On the problem of large gcd for disjoint residue classes

Abstract

Consider $k$ pairwise disjoint residue classes $a_i(\mathrm{mod}{m}_i)$. We prove that \[ \max_{1\leq i<j\leq k}\gcd(m_i,m_j) \gg k\exp\!\left(-(2+o(1)) \sqrt{\frac{\log k}{\log\log k}}\right). \] The proof uses a complete graph whose edges are colored by the gcds of the corresponding moduli, together with a structural lemma, a sieve-theoretic partition, Möbius inversion, and the discrete Fourier transform.

arXiv comment19 pages