Problem 1741

1. Initial Setup:
Let $n$ and $m$ be integers greater than 1, and let $a_1, a_2, \dots, a_m$ be positive integers not greater than $n^m$. We need to prove that there exist positive integers $b_1, b_2, \dots, b_m$ not greater than $n$ such that
$$\gcd(a_1 + b_1, a_2 + b_2, \dots, a_m + b_m) < n.$$

2. Vector Definition:
Since $b_i \in \{1, 2, \ldots, n\}$, we have $n^m$ vectors $(b_1, b_2, \ldots, b_m)$. Label them as $v_i$ where $i$ ranges from 1 to $n^m$. The ordering of the $i$-s does not matter.

3. GCD Definition:
Define
$$l_{v_i} := \gcd(a_1 + b_1, \ldots, a_m + b_m)$$
where $v_i$ is the vector associated with $(b_1, \ldots, b_m)$.

4. Claim 1:
If $a_i = a_j$ for any $i < j$, then the problem condition holds true.
- Proof:
If $a_i = a_j$, consider vectors $v_x = (b_1, \ldots, b_i, \ldots, b_j, \ldots, b_m)$ and $v_y = (b_1, \ldots, b_i + 1, \ldots, b_j, \ldots, b_m)$. Note that $p \mid u$ and $p \mid u + 1$ cannot both hold true for any prime $p$. Therefore, at least one of $l_{v_x}$ or $l_{v_y}$ equals 1. Since $n > 1$, we are done here. $\blacksquare$

5. Assumption for Contradiction:
Assume on the contrary that $l_{v_i} \ge n$ for all the $n^m$ vectors $v_i$.

6. Claim 2:
We cannot have $l_{v_i} = l_{v_j}$ for any $i \ne j$, i.e., all the $l_{v_i}$ are distinct numbers.
- Proof:
Assume on the contrary that $i \ne j$ and $l_{v_i} = l_{v_j}$. Since $i \ne j$, at least one of the $b_i$-s is different for both, say $b_i \in v_i$ and $b_i' \in v_j$ with $b_i \ne b_i'$. Then
$$l_{v_i} \mid (a_i + b_i) \quad \text{and} \quad l_{v_i} \mid (a_i + b_i') \implies l_{v_i} \mid (b_i - b_i') \implies n \le l_{v_i} \le |b_i - b_i'|$$
which is a contradiction as $1 \le b_i, b_i' \le n$. $\blacksquare$

7. **Range of $l_{v_i}$:**
Note that
$$n \le l_{v_i} \le \max_{1 \le i \le n} \{a_i + b_i\} \le n^m + n$$
for all $1 \le i \le n^m$.

8. Maximum Value Case:
If $l_{v_i} = n^m + n$ for some $v_i$, then we must have $v_i = (n, n, \ldots, n)$ (i.e., $b_1 = \cdots = b_m = n$) and $a_1 = a_2 = \cdots = a_m = n^m$. Since $m \ge 2$, we have at least two equal numbers $a_1, a_2$, leading to a contradiction by Claim 1.

9. Distinct Values:
Thus,
$$\{l_{v_1}, l_{v_2}, \ldots, l_{v_{n^m}}\} \equiv \{n, n+1, \ldots, n^m + n - 1\}$$
i.e., the two sets are equal. Hence $l_{v_i} = n^m + n - 1$ for some $i$.

10. **Contradiction for $m \ge 3$:**
If $m \ge 3$, then we will find two equal numbers among $\{a_1, a_2, a_3\}$, leading to a contradiction by Claim 1.

11. **Case $m = 2$:**
For $m = 2$, we must have $\{a_1, a_2\} \equiv \{n^2, n^2 - 1\}$. Suppose $a_1 = n^2$ and $a_2 = n^2 - 1$. Then choose $b_1 = b_2 = n$. Hence
$$\gcd(a_1 + b_1, a_2 + b_2) = \gcd(n^2 + n, n^2 + n - 1) = 1 < n,$$
a contradiction.

12. Conclusion:
Hence, we will find a $v_i$ with $l_{v_i} < n$, as desired. $\blacksquare$