= Solution
Let $\chi$ be the quadratic character, equivalently the <Legendre symbol>. Zero is included among the square <residue classes>. For every <integer> $n$ its square-class indicator is
$$
1_{\{n\bmod q\text{ is a square}\}}=\frac{1+\chi(n)+1_{q\mid n}}2.
$$
For a nonzero <quadratic residue> the right side is one, for a nonresidue it is zero, and for a multiple of $q$ it is one. Summing over the interval, the character contribution is $O(\sqrt q\log q)$ by the previous part, while the number of multiples of $q$ is $N/q+O(1)$. Thus the required count is
$$
\boxed{\frac{N(q+1)}{2q}+O(\sqrt q\log q).}
$$
This counts the <integers> in the interval whose <residue classes> are squares. When the interval exceeds one period, repeated appearances are counted; the displayed main term could not describe a count of distinct <residue classes> for arbitrary $N$.
Back to article page
