Number of solutions modulo n^2

Question

Let $n \ge 2$ be an integer.Prove that the number of integers $m$ such that $0 \le m \le n^2-1$ for which there are no solutions to $x^n+y^n \equiv m \pmod{n^2}$ is at least $\binom{n}{2}$. I only proved that if $x \equiv y \pmod{n}$,then $x^n \equiv y^n \pmod{n^2}$ but don't know how to proceed.

Answer 1

You are almost done. Your argument shows that the number of sums you can get is the same as the number of sums if you choose $x, y$ from $\{0, \dots, n-1\}$ which gives you $n^2$ sums, but actually $x^n + y^n = y^n + x^n,$ so the maximal number of sums is $\frac{(n+1)n}2,$ which means that $n^2 - \frac{(n+1)n}2 = \binom{n}2$ sums cannot be attained.