For which $n$ does $\{a^2:a\in\mathbb{Z}\}$ contain the additive inverse of each element modulo $n$? Take $S=\{a^2:a\in\mathbb{Z}\}$. Now, for which $n$ does $S$ contain the additive inverse of each element modulo $n$?
For all $a,b,x,y\in\mathbb{Z}$ we have:
$$(ax+by)^2\equiv-(ay-bx)^2\pmod{a^2+b^2}$$
and since all numbers $n\equiv 1\pmod 4$ can be written as the sum of two coprime squares, we can find $a,b\in\mathbb{N}$ such that $ax+by$ can take on all values in $\Bbb{Z}$, so the above congruences is enough to show the existance of inverses. The congruence doesn't work with numbers $n\equiv 3\pmod 4$, since those can't be written as the sum of two squares. Numbers of the form $n\equiv 0\pmod 4$ can't be written as the sum of two coprime squares, so that doesn't work either. $n\equiv 2\pmod 4$ seems to work sometimes.
The first few 'non-trivial' (read: not congruent to $1\pmod 4$) values of $n$ I found were:
$$2,10,26,34,50,58,74,82$$
Question: is there a simple (fast) way to determine for any given $n\in\Bbb{N}$ whether or not $S$ does contain the additive inverse of each element modulo $n$?
I found A008784 which appears to have all values of $n$. Apparentely these are the positive integers with prime factors all of the form $4k+1$ except for at most one factor of $2$, but I can't seem to find a proof of that.
Edit: as Thomas Andrews points out, not all numbers congruent to $1$ modulo $4$ can be expressed as sums of two squares, though I'm pretty sure primes congruent to $1$ modulo $4$ can.
 A: Note that $1$ is a square mod any $n$. In particular, this implies that we necessarily must have that $-1$ is a square in order for your condition to hold. Conversely, suppose that $-1\equiv a^2\pmod{n}$. Then, for any $b$ we have $(ab)^2=-b^2\pmod{n}$, so your condition would hold. Note that asking that $-1$ be a square mod $n$ is equivalent to asking that it be a square mod every prime power dividing $n$, so let us examine when $-1$ is a square mod $p^n$.
If $p$ is an odd prime, then the multiplicative group mod $p^n$ is the cyclic group $Z_{(p-1)p^{n-1}}$. Note that $-1$ is the unique element of order $2$ in this group. Thus, it is a square if and only if $4$ divides the order of the group, which is $(p-1)p^{n-1}$. In particular, this happens precisely when $p\equiv 1\pmod{4}$. Lastly, consider what happens when $p=2$. Note that $-1$ is not a square mod $p^2=4$ and is a square mod $p=2$.
Thus, our answer is that this is true precisely when the prime factorization of $n$ contains only primes that are $1$ mod $4$ and possibly the prime $2$ with multiplicity $1$.
A: Okay so let $a^2\in S$ and we want to know if $-a^2\mod n\in S$. $-a^2\in S$ if and only if
$$-a^2\equiv b^2\mod n$$
for some $b\in\mathbb{Z}$. This is the case exactly when $-a^2$ is a quadratic residue modulo $n$. In order for this to hold we must have that for all odd primes $p\mid n$,
$$\left(\frac{-a^2}{p}\right)=\left(\frac{a^2}{p}\right)\cdot \left(\frac{-1}{p}\right)=\left(\frac{-1}{p}\right)=1$$
which requires that $p\equiv 1\mod 4$ (thus to satisfy the criterion $n$ must have all its odd prime factors $\equiv 1\mod 4$).
Now suppose $4\mid n$. We must have that $b^2\equiv -1\mod 4$ for some $b$, however this is clearly not the case because $b^2\equiv 0\text{ or } 1\mod 4$. Thus we can have at most $2\mid\mid n$. If $2\mid\mid n$ it is clear that we can find a $b$ such that $b^2\equiv -a^2\mod 2$, just match their parities.
Thus we have shown the condition you found to be necessary, now it just needs to be shown to be sufficient. For it to be sufficient we just need to show $-1$ is a quadratic residue mod all $n$ satisfying this criterion. Let $n=2^{\gamma}p_1^{a_1}p_2^{a_2}\dots p_j^{a_j}$. Clearly $-1$ is a quadratic residue mod $2^{\gamma}$ since $\gamma=0 \text{ or } 1$ and since $p_i\equiv 1\mod 4$ and $\text{gcd}(-1, p_i)=1$, $-1$ is a quadratic residue modulo $p_i^{a_i}$. Thus there exists integers $b_0, b_1, \dots, b_j$ such that
$$\begin{array}{c}
-1\equiv b_0^2\mod 2^{\gamma} \\
-1\equiv b_1^2\mod p_1^{a_1} \\
\vdots \\
-1\equiv b_j^2\mod p_j^{a_j} 
\end{array}$$
Now we are looking for a $b$ that simultaneously satisfies $b^2\equiv -1\mod 2^{\gamma}$, $b^2\equiv -1\mod p_1^{a_1}$, $\dots$, $b^2\equiv -1\mod p_j^{a_j}$ which would imply $b^2\equiv -1\mod n$. To find this $b$ it is sufficient to have $b$ satisfy
$$\begin{array}{c}
b\equiv b_0\mod 2^{\gamma} \\
b\equiv b_1\mod p_1^{a_1} \\
\vdots \\
b\equiv b_j\mod p_j^{a_j}
\end{array}$$
which by the CRT we know such a $b$ exists. Thus if $n$ satisfies our criterion, $-1$ is a quadratic residue and we see the criterion is sufficient for implying $S$ contains all additive inverses modulo $n$.
