EGMO 2015 Problem 3

Let $n, m$ be integers greater than 1 , and let $a_{1}, a_{2}, \ldots, a_{m}$ be positive integers not greater than $n^{m}$. Prove that there exist positive integers $b_{1}, b_{2}, \ldots, b_{m}$ not greater than $n$, such that

$$\operatorname{gcd}\left(a_{1}+b_{1}, a_{2}+b_{2}, \ldots, a_{m}+b_{m}\right)<n$$

where $\operatorname{gcd}\left(x_{1}, x_{2}, \ldots, x_{m}\right)$ denotes the greatest common divisor of $x_{1}, x_{2}, \ldots, x_{m}$.