MathDB

6

Part of 2014 USAMO

Problems(1)

nth root of a, b in O(sqrt(n))

Source: 2014 USAMO problem 6

4/30/2014
Prove that there is a constant c>0c>0 with the following property: If a,b,na, b, n are positive integers such that gcd⁡(a+i,b+j)>1\gcd(a+i, b+j)>1 for all i,j∈{0,1,…n}i, j\in\{0, 1, \ldots n\}, thenmin⁡{a,b}>cn⋅nn2.\min\{a, b\}>c^n\cdot n^{\frac{n}{2}}.
USA(J)MOUSAMOinequalitieslogarithmsPutnam