MathDB
Pairwise gcd is equal to gcd of all elements

Source: China TSTST 3 Day 2 Problem 2

March 18, 2017
greatest common divisornumber theory

Problem Statement

Show that there exists a positive real CC such that for any naturals H,NH,N satisfying H≥3,N≥eCHH \geq 3, N \geq e^{CH}, for any subset of {1,2,…,N}\{1,2,\ldots,N\} with size ⌈CHNln⁡N⌉\lceil \frac{CHN}{\ln N} \rceil, one can find HH naturals in it such that the greatest common divisor of any two elements is the greatest common divisor of all HH elements.
Back to ProblemsView on AoPS