IMO 2019 Shortlisted Problems

$n$ is divisible by $\phi \left(p^e\right)$ for every prime power $p^e$ exactly dividing $N$. This property ensures that all $n^{\text{th}}$ powers are congruent to $0$ or $1$ modulo each such prime power $p^e$, and hence that any sum of $m$ pairwise coprime $n^{\text{th}}$ powers is congruent to $m$ or $m-1$ modulo $p^e$, since at most one of the $n^{\text{th}}$ powers is divisible by $p$. Thus, if $k$ denotes the number of distinct prime factors of $N$, we find by the Chinese Remainder Theorem at most $2^{k}m$ residue classes modulo $N$ which are sums of at most $m$ pairwise coprime $n^{\text{th}}$ powers. In particular, if $N>2^{k}m$ then there are infinitely many positive integers not expressible as a sum of at most $m$ pairwise coprime $n^{\text{th}}$ powers. It thus suffices to prove that there are arbitrarily large pairs $(n,N)$ of integers satisfying $(†)$ such that $$N>c\cdot 2^{k}n\log (n)$$ for some positive constant $c$. We construct such pairs as follows. Fix a positive integer $t$ and choose (distinct) prime numbers $p\mid 2^{2^{t-1}}+1$ and $q\mid 2^{2^t}+1$; we set $N=pq$. It is well-known that $2^t\mid p-1$ and $2^{t+1}\mid q-1$, hence $$n=\frac{(p-1)(q-1)}{2^t}$$ is an integer and the pair ( $n,N$ ) satisfies ( $†$ ). Estimating the size of $N$ and $n$ is now straightforward. We have $${\log }_2(n)⩽2^{t-1}+2^t-t<2^{t+1}<2\cdot \frac{N}{n}$$ which rearranges to $$N>\frac{1}{8}\cdot 2^{2}n{\log }_2(n)$$

Solution 2, obtaining better bounds. As in the preceding solution, we seek arbitrarily large pairs of integers $n$ and $N$ satisfying $(†)$ such that $N>c{2}^{k}n\log (n)$. This time, to construct such pairs, we fix an integer $x⩾4$, set $N$ to be the lowest common multiple of $1,2,\dots ,2x$, and set $n$ to be twice the lowest common multiple of $1,2,\dots ,x$. The pair $(n,N)$ does indeed satisfy the condition, since if $p^e$ is a prime power divisor of $N$ then $\frac{\phi \left(p^e\right)}{2}⩽x$ is a factor of $\frac{n}{2}={\mathrm{lcm}}_{r⩽x}(r)$. Now $2N/n$ is the product of all primes having a power lying in the interval ( $x,2x$ ], and hence $2N/n>x^{\pi (2x)-\pi (x)}$. Thus for sufficiently large $x$ we have $$\log \left(\frac{2N}{2^{\pi (2x)}n}\right)>(\pi (2x)-\pi (x))\log (x)-\log (2)\pi (2x)\sim x$$ using the Prime Number Theorem $\pi (t)\sim t/\log (t)$. On the other hand, $n$ is a product of at most $\pi (x)$ prime powers less than or equal to $x$, and so we have the upper bound $$\log (n)⩽\pi (x)\log (x)\sim x$$ again by the Prime Number Theorem. Combined with the above inequality, we find that for any $ϵ>0$, the inequality $$\log \left(\frac{N}{2^{\pi (2x)}n}\right)>(1-ϵ)\log (n)$$ holds for sufficiently large $x$. Rearranging this shows that $$N>2^{\pi (2x)}{n}^{2-ϵ}>2^{\pi (2x)}n\log (n)$$ for all sufficiently large $x$ and we are done.