Q3 Matemática  (EGMO 2015)

Sejam $n,m$ inteiros maiores que $1$, e sejam $a_1,a_2,\dots ,a_m$ inteiros positivos não maiores que $n^m$. Prove que existem inteiros positivos $b_1,b_2,\dots ,b_m$ não maiores que $n$, tais que $$\gcd (a_1+b_1,a_2+b_2,\dots ,a_m+b_m)<n,$$ onde $\gcd (x_1,x_2,\dots ,x_m)$ denota o máximo divisor comum de $x_1,x_2,\dots ,x_m$.