Европейская математическая олимпиада среди девочек (EGMO). 2015 год. Беларусь

Пусть $n, m$ — натуральные числа, большие 1, и пусть $a_{1}, a_{2}, \ldots, a_{m}$ — натуральные числа, не превосходящие $n^{m}$. Докажите, что существуют натуральные числа $b_{1}, b_{2}, \ldots, b_{m}$, не превосходящие $n$, такие, что $$\text{НОД}\left(a_{1}+b_{1}, a_{2}+b_{2}, \ldots, a_{m}+b_{m}\right) < n,$$ где $\text{НОД}\left(x_{1}, x_{2}, \ldots, x_{m}\right)$ обозначает наибольший общий делитель чисел $x_{1}, x_{2}, \ldots, x_{m}$.