The original question has been answered (they are always a cyclic group). Perhaps slightly more interesting is:
Fix $m\gt 0$. Then the subset of the units modulo $m$ that are squares forms a subgroup of the invertible elements modulo $m$. When is this subgroup cyclic?
If there is a primitive root modulo $m$ (that is, if the group of units modulo $m$ is cyclic), then the property holds. This occurs when $m$ is a power of an odd prime, twice a power of an odd prime, $m=2$, or $m=4$.
It also holds if $m=8$, since then the only quadratic residue is $1$, so the group of quadratic residues is cyclic. In fact, it holds if $m=2^n$ is a power of $2$, the result holds: because the group of units modulo $2^n$ is isomorphic to $C_{2^{n-2}}\times C_2$ (where $C_k$ is the cyclic group of order $k$), so the group of squares is isomorphic to $C_{2^{n-3}}$, which is cyclic.
Other nontrivial examples include $m=3p^a$ or $m=6p^a$ where $p$ is an odd prime and $a\gt 0$, $m=35 = 5\times 7$ (or more generally, $m=5^a 7^b$); and many others.
To get the complete answer, factor $m$ into primes,
$$ m = p_1^{a_1}\cdots p_r^{a_r}$$
where $p_1\lt p_2\lt\cdots\lt p_r$ are primes, and $a_r\gt 0$. By the Chinese Remainder Theorem, the group of units modulo $m$ is
$$\left(\mathbb{Z}/m\mathbb{Z}\right)^* = \prod_{i=1}^r \left(\mathbb{Z}/p_i^{a_i}\mathbb{Z}\right)^*.$$
The group of units modulo $p_i^{a_i}$ is
- Cyclic of order $(p_i-1)p_i^{a_i-1}$ if $p_i$ is odd;
- Trivial if $p_i=2$ and $a_i = 1$;
- Isomorphic to $\displaystyle C_{2^{a_i-2}}\times C_2$ if $p_i=2$ and $a_i\gt 1$.
The group of squares of invertible elements modulo $m$ is then isomorphic to a product of groups of the form
- Cyclic of order $\frac{p_i-1}{2}(p_i^{a_i-1})$ if $p_i$ is odd;
- Trivial if $p_i=2$ and $a_i\leq 2$;
- Cyclic of order $2^{a_i-3}$ if $p_i=2$ and $a_i\geq 3$.
The product is cyclic if and only if the orders of the cyclic factors are pairwise relatively prime.
This gives:
Theorem. Let $m$ be a positive integer, and let $p_1,p_2,\ldots,p_r$ be the distinct prime divisors of $m$, $p_1\lt p_2\lt\cdots\lt p_r$. Let $\varphi$ be Euler's totient function. The subgroup of squares of the invertible elements modulo $m$ is cyclic if and only if:
- For $m$ odd,
- $\displaystyle\gcd\left(\frac{\varphi(p_i^{a_i})}{2},\frac{\varphi(p_j^{a_j})}{2}\right) = 1$ for all $1\leq i\lt j\leq r$.
- For $m$ even,
- $\displaystyle\gcd\left(\frac{\varphi(p_i^{a_i})}{2},\frac{\varphi(p_j^{a_j})}{2}\right) = 1$ for $1\lt i\lt j\leq r$; and
- if $2^a$ is the largest power of $2$ that divides $m$ and $a\gt 3$, then $p_i\equiv 3\pmod{4}$ for all $i\gt 1$.
It is straightforward now to show (e.g., using Dirichlet's theorem on primes in arithmetic sequences) that there are $m$ with arbitrarily many distinct prime divisors for which the subgroup of squares of the units modulo $m$ is cyclic.
Yes, there's a formula, though not quite as simple: the sum is
$$
\frac12 \left( {q \choose 2} - \frac2w qh \right),
$$
where $h$ is the class number of the quadratic imaginary field
${\bf Q}(\sqrt{-p})$, and $w$ is the number of roots of unity
in that field, so that the factor $2/w$ is just $1$ except for $q=3$
when $2/w = 1/3$.
This is obtained by writing the sum of the residues as
$\frac12 \sum_{r=1}^{p-1} (1+(r/p)) r$, where $(r/p)$ is the Legendre symbol.
The $\sum_r r$ part of this gives $q \choose 2$, and the formula $-2qh/w$ for the
$\sum_r (r/p) r$ part is classical (the factor $2/w$ arises via the
Dirichlet class number formula, see for instance the $d<0$ part of
equation (2) in MathWorld's
"Class Number" page).
[The formula for $q \equiv 1 \bmod 4$
is simple because in that case the identity $(r/p) = (-r/p) = ((p-r)/p)$ yields
$\sum_{r=1}^{p-1} (r/p) r = 0$ by symmetry.]
Best Answer
More direct, but less elegant than darij's proof:
We have $\sum_{k=1}^{p-1} k^2 = \frac{p(p-1)(2p-1)}{6}$. This sum has each quadratic residue repeated twice, so, assuming $p\neq 2$, the sum of the quadratic residues is $\frac{p(p-1)(2p-1)}{6} \cdot 2^{-1} \pmod{p}$. If $p\neq 3$, this is clearly $0\pmod{p}$.