Suppose without loss of generality that $a_{1}$ is the smallest of the $a_{i}$. If $a_{1} \geq n^{m}-1$, then the problem is simple: either all the $a_{i}$ are equal, or $a_{1}=n^{m}-1$ and $a_{j}=n^{m}$ for some $j$. In the first case, we can take (say) $b_{1}=1, b_{2}=2$, and the rest of the $b_{i}$ can be arbitrary, and we have

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

In the second case, we can take $b_{1}=1, b_{j}=1$, and the rest of the $b_{i}$ arbitrary, and again

$$\operatorname{gcd}\left(a_{1}+b_{1}, a_{2}+b_{2}, \ldots, a_{m}+b_{m}\right) \leq \operatorname{gcd}\left(a_{1}+b_{1}, a_{j}+b_{j}\right)=1$$

So from now on we can suppose that $a_{1} \leq n^{m}-2$.
Now, let us suppose the desired $b_{1}, \ldots, b_{m}$ do not exist, and seek a contradiction. Then, for any choice of $b_{1}, \ldots, b_{m} \in\{1, \ldots, n\}$, we have

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

Also, we have

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

Thus there are at most $n^{m}-1$ possible values for the greatest common divisor. However, there are $n^{m}$ choices for the $m$-tuple $\left(b_{1}, \ldots, b_{m}\right)$. Then, by the pigeonhole principle, there are two $m$-tuples that yield the same values for the greatest common divisor, say $d$. But since $d \geq n$, for each $i$ there can be at most one choice of $b_{i} \in\{1,2, \ldots, n\}$ such that $a_{i}+b_{i}$ is divisible by $d$ - and therefore there can be at most one $m$-tuple $\left(b_{1}, b_{2}, \ldots, b_{m}\right)$ yielding $d$ as the greatest common divisor. This is the desired contradiction.