IMC 2010 · Day 1 · P4

Assume that $n > 1$. Notice that $n$ may be replaced by any prime divisor $p$ of $n$. Moreover, $a$ and $b$ should be coprime, otherwise the numbers not divisible by the greatest common divisor of $a, b$ cannot be represented as $a x^n + b y^n$.

If $p = 2$, then the number of the form $a x^2 + b y^2$ takes not all possible remainders modulo 8. If, say, $b$ is even, then $a x^2$ takes at most three different remainders modulo 8, $b y^2$ takes at most two, hence $a x^2 + b y^2$ takes at most $3 \times 2 = 6$ different remainders. If both $a$ and $b$ are odd, then $a x^2 + b y^2 \equiv x^2 \pm y^2 \pmod 4$; the expression $x^2 + y^2$ does not take the remainder 3 modulo 4 and $x^2 - y^2$ does not take the remainder 2 modulo 4.

Consider the case when $p \ge 3$. The $p$th powers take exactly $p$ different remainders modulo $p^2$. Indeed, $(x + kp)^p$ and $x^p$ have the same remainder modulo $p^2$, and all numbers $0^p, 1^p, \dots, (p-1)^p$ are different even modulo $p$. So, $a x^p + b y^p$ take at most $p^2$ different remainders modulo $p^2$. If it takes strictly less then $p^2$ different remainders modulo $p^2$, we get infinitely many non-representable numbers. If it takes exactly $p^2$ remainders, then $a x^p + b y^p$ is divisible by $p^2$ only if both $x$ and $y$ are divisible by $p$. Hence if $a x^p + b y^p$ is divisible by $p^2$, it is also divisible by $p^p$. Again we get infinitely many non-representable numbers, for example the numbers congruent to $p^2$ modulo $p^3$ are non-representable.