Killer lemma:If $x \equiv y (mod n)$ then $x^n \equiv y^n (mod n^2)$. The rest is just counting arguments.

Claim: If $x \equiv y \mod n$ then $x^n \equiv y^n \mod n^2$. Proof: Use the division algorithm to write $x=an+b$ then we have from Newton's binomial identity $$(an+b)^n=b^n+\binom{n}{1}(an)b^{n-1}+\binom{n}{2}(an)^2b^{n-2}+\dots \equiv b^n \mod n^2$$which proves the claim. Now we will count the number of $m$s such that the equation $ x^n+y^n \equiv m \mod n^2$ has a solution, for that task we know from the lemma the $x^n$ can only take $n$ values so there are at most $\binom{n}{2}$ values when $x^n$ and $y^n$ are distinct modulo $n$ and $n$ values when $x^n $ and $y^n$ are the same modulo $n$ hence the total number of $m$s with a solution is at most $\binom{n}{2}+n=\frac{(n)(n+1)}{2}$ so the number $m$s with no solutions is at least $$n^2-\frac{(n)(n+1)}{2}=\frac{(n)(n-1)}{2}=\binom{n}{2}.$$

if we prove that the number of $y$ such that $y = x^{n}$ modoulo $n^2$ is at most $n+1$ then the problem will solve. by use the first root we have that the number of $y$ such that $y = x^{P_i^{a_i}}$ modulo $P_i^{2.a_i}$ is at most $P_i^{a_i}$. now if $n = 2^a.P_1^{a_1}.P_2^{a_2}...P_k^{a_k}$ then by use CRT and the fact in line before we have what we want. note that for $2^a$ we can use this fact: for any $n>=3$ we have that $1,3,3^2,...,3^{2^n-1}$ and $-1,-3,-3^2,...,-3^{2^n-1}$.

Fatemeh06 wrote: if we prove that the number of $y$ such that $y = x^{n}$ modoulo $n^2$ is at most $n+1$ then the problem will solve. by use the first root we have that the number of $y$ such that $y = x^{P_i^{a_i}}$ modulo $P_i^{2.a_i}$ is at most $P_i^{a_i}$. now if $n = 2^a.P_1^{a_1}.P_2^{a_2}...P_k^{a_k}$ then by use CRT and the fact in line before we have what we want. note that for $2^a$ we can use this fact: for any $n>=3$ we have that $1,3,3^2,...,3^{2^n-1}$ and $-1,-3,-3^2,...,-3^{2^n-1}$. can anyone see if this is correct or not?