Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 23 / 1 / e / 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 isFor 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 isThis 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$.