MathDB
[EGMO3] GCD Bounds

Source: EGMO 2015, Problem 3

April 16, 2015
number theoryEGMOgreatest common divisorEGMO 2015

Problem Statement

Let n,mn, m be integers greater than 11, and let a1,a2,…,ama_1, a_2, \dots, a_m be positive integers not greater than nmn^m. Prove that there exist positive integers b1,b2,…,bmb_1, b_2, \dots, b_m not greater than nn, such that gcd⁡(a1+b1,a2+b2,…,am+bm)<n, \gcd(a_1 + b_1, a_2 + b_2, \dots, a_m + b_m) < n, where gcd⁡(x1,x2,…,xm)\gcd(x_1, x_2, \dots, x_m) denotes the greatest common divisor of x1,x2,…,xmx_1, x_2, \dots, x_m.
Back to ProblemsView on AoPS