Taiwan IMO Selection Camp, 2021

Solution. We first prove (a). Let $N, C_1, C_2$ be some positive integers to be determined. Let $P$ be the product of all primes at most $\max\{a, b, 2n+4\}$. Let $S_1 = \{Pn + C_1 : n \in [N]\}$ and $S_2 = \{Pn + C_2 : n \in [N]\}$. For each prime $p \in (\max\{a, b, 2n+4\}, \sqrt{N})$, we first count the number of $(x, y) \in S_1 \times S_2$ that satisfies $p^2 \mid ax^n + by^n$. For each $y \in S_2$, if $p \mid y$, then we also need $p \mid x$, showing that there are at most $(N/p + 1)$ values for $x$ in $S_1$ such that $p^2 \mid ax^n + by^n$ (here we use the fact that $\gcd(p, P) = 1$). If $p \nmid y$, then we know that there are at most $n$ roots for $ax^n + by^n \equiv 0 \pmod{p}$. Since $p \nmid n$, each solution modulo $p$ lifts uniquely to a solution modulo $p^2$, showing that there are at most $n(N/p^2 + 1)$ values for $x$ in $S_1$ such that $p^2 \mid ax^n + by^n$ (here we use the fact that $\gcd(p, P) = 1$ once again). Therefore, in total, there are at most
$$\left(\frac{N}{p} + 1\right)^2 + \left(N - \frac{N}{p} - 1\right) \cdot n \left(\frac{N}{p^2} + 1\right) < \frac{(2n + 4)N^2}{p^2}$$
pairs of $(x, y) \in S_1 \times S_2$ that satisfy $p^2 \mid ax^n + by^n$. Since we know that
$$\sum_{i=2n+5}^{\infty} \frac{1}{i(i-1)} = \sum_{i=2n+5}^{\infty} \left( \frac{1}{i-1} - \frac{1}{i} \right) = \frac{1}{2n+4},$$
we have that
$$\sum_{\text{prime } p \ge 2n+5} \frac{2n+4}{p^2} < \sum_{i=2n+5}^{\infty} \frac{2n+4}{i(i-1)} = 1.$$
As a consequence, we know that for every $C_1, C_2, N$, there exists a pair $(x, y) \in S_1 \times S_2$ such that for any prime $p \in (\max\{a, b, 2n+4\}, \sqrt{N})$ we have $p^2 \nmid ax^n + by^n$.
Next, we will choose $C_1, C_2$ properly to deal with the case $p \le \max\{a, b, 2n+4\}$. For each prime $p \le \max\{a, b, 2n+4\}$, if $p \nmid a$ then we can choose $C_1 \equiv 1 \pmod{p}$

and $C_2 \equiv 0 \pmod{p}$; otherwise, we know by the condition that $p \nmid b$, and so we can choose $C_1 \equiv 0 \pmod{p}$ and $C_2 \equiv 1 \pmod{p}$. By the Chinese Remainder Theorem, we know that we can choose $1 \le C_1, C_2 \le P$ such that the above conditions hold for all primes $p \le \max\{a, b, 2n+4\}$. As a consequence, we now also have that for any prime $p \le \max\{a, b, 2n+4\}$ and any $(x, y) \in S_1 \times S_2$, we have $p \nmid ax^n + by^n$.
With this choice of $C_1, C_2$, we know that for all $N$, we can choose $(x, y) \in S_1 \times S_2$ such that $p^2 \nmid ax^n+by^n$ for all $p < \sqrt{N}$. Note that $ax^n+by^n \le 2\max\{a, b\}P^n(N+1)^n < 2^{n+1} \max\{a, b\}P^n N^n$, and also that if $p$ is a prime such that $p^2 \mid ax^n+by^n$ then $p \ge \sqrt{N}$. We thus have the number of distinct primes $p$ satisfying $p^2 \mid ax^n + by^n$ is at most
$$\log_{\sqrt{N}} 2^{n+1} \max\{a, b\}P^n N^n = 2n + \log_{\sqrt{N}} 2^{n+1} \max\{a, b\}P^n,$$
which is less than $2n+1$ if $N$ is large enough. Thus, we know that there exist $x, y \in \mathbb{N}$ such that there are at most $2n$ distinct primes $p$ that satisfy $p^2 \mid ax^n + by^n$.
Now we use (a) to prove (b). For each prime factor $p$ of $a_k$, we know that there exists $i(p) \in [k-1]$ so that $p \nmid a_{i(p)}$. We can thus set $x_j \equiv \delta_{i(p),j} \pmod{p}$ so that $p \nmid a_1x_1^n + a_2x_2^n + \dots + a_{k-1}x_{k-1}^n$. By the Chinese Remainder Theorem, we know that there exist positive integers $x_1, \dots, x_{k-1}$ such that $x_j \equiv \delta_{i(p),j} \pmod{p}$ for all $j \in [k-1]$ and prime factors $p$ of $a_k$. Thus, we have that $a_1x_1^n + a_2x_2^n + \dots + a_{k-1}x_{k-1}^n$ and $a_k$ are coprime. We can thus choose $x, y \in \mathbb{N}$ by (a) so that $(a_1x_1^n + \dots + a_{k-1}x_{k-1}^n)x^n + a_ky^n$ is $n$-good. Therefore, $a_1(x_1x)^n + \dots + a_{k-1}(x_{k-1}x)^n + a_ky^n$ is $n$-good, as desired.