2015 유럽여학생수학올림피아드 3번문제

$1$보다 큰 양의 정수 $n$, $m$에 대하여 정수 $n^m$보다 크지 않은 양의 정수의 수열 $a_1,a_2,\ldots,a_m$이 주어져있다. 이때, 다음 조건을 만족하는 $n$보다 크지 않은 양의 정수 $b_1,b_2,\ldots,b_m$이 존재함을 증명하라. \[ \operatorname{gcd}(a_1+b_1,a_2+b_2,\ldots,a_m+b_m)\lt n\]단, $\operatorname{gcd}(x_1,x_2,\ldots,x_m)$은 $x_1$, $x_2$, $\ldots$, $x_m$의 최대공약수를 뜻한다.