On the problem of large gcd for disjoint residue classes

2026/07/27 by Jan Fornal, Yu-Chen Sun
Mathematics · #math.CO #math.NT

paper · pdf

Abstract

Consider k pairwise disjoint residue classes a_i \pmodm_i. We prove that max_{1≤ i<j≤ k}gcd(m_i,m_j) ≫ kexp (-(2+o(1)) √((log k)/(loglog k))). 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.

Related

• On some applications of GCD sums to Arithmetic Combinatorics
• Strong divisibility and lcm-sequences
• Distribution of factorials modulo p
• Studying the divisibility of power LCM matrics by power GCD matrices on gcd-closed sets
• On partitions of ℤ_m with the same representation function