Taiwan IMO 1J, 2020

First, we prove the following lemma.

Lemma. For any positive integers $X, A$ and $B$ with $A \neq B$ we have
$$\text{gcd}(X^A + A, X^B + B) < A^B + B^A.$$

Proof of lemma. Note that $X^B + B$ divides $X^{AB} - (-B)^A$, and that
$$\text{gcd}(X^A + A, (X^A)^B - (-B)^A) = \text{gcd}(X^A + A, (-A)^B - (-B)^A).$$
We now have two cases. If $A^B \neq B^A$, then $(-A)^B - (-B)^A \neq 0$, and
$$\text{gcd}(X^A + A, X^B + B) \le |(-A)^B - (-B)^A| \le A^B + B^A.$$
The only other case is when $(A, B) = (2, 4)$ or $(A, B) = (4, 2)$. But here we can check it manually, since $\text{gcd}(X^2 + 2, X^4 + 4) = \text{gcd}(X^2 + 2, 8) \le 8$. ■

Now, we claim that for every $1 \le m < 100$ there exists a prime power $P_m$ dividing $N^m+m$ which does not divide any other $N^c+c$ (for $1 \le c < 100$). This will immediately solve the problem, because no two of the $P_i$ can have a common factor.

Assume for contradiction this is not the case. Then for some $m$, it must be the case that
$$N^m + m \le \prod_{1 \le k < 100 \atop k \ne m} \text{gcd}(N^m + k, N^k + m) \le \prod_{1 \le k < 100 \atop k \ne m} (m^k + k^m).$$

Let $\alpha$ be a real number such that $m \le \alpha^m$ for all integers $m$. We may then write
$$\begin{align*} N &< \prod_{\substack{1 \le k < 100 \\ k \ne m}} (m^k + k^m)^{1/m} \\ &< \prod_{1 \le k < 100} ((m^{1/m})^k + k) \\ &< \prod_{1 \le k < 100} (\alpha^k + k) \\ &= \alpha^{4950} \prod_{1 \le k < 100} \left(1 + \frac{k}{\alpha^k}\right) \\ &< \alpha^{4950} \cdot \left(1 + \frac{\frac{1}{\alpha} + \frac{1}{\alpha^2} + \dots + \frac{99}{\alpha^{99}}}{99}\right)^{99} \end{align*}$$
with the last line being AM-GM. If we take even the crude bound $\alpha = 2$ now, then we easily get an upper bound of $2^{4950} (1 + \frac{2}{99})^{100} < 2^{5000}$, which is a contradiction. This concludes the proof.