Number of quadratic residues in an interval Using the Pólya-Vinogradov inequality, one can apparently show that the number of quadratic residues modulo $q$ in any interval of length $N$ is $N/2 + O(q^{1/2}\log q)$.
I feel like I am missing something really simple here, because I do not see how this holds. If we take $q$ to be prime, then the number of quadratic residues modulo $q$ is $(q-1)/2$ (excluding $0$) so taking $k$ of these intervals, say from $1$ to $kq$, we get $k (q-1)/2$ quadratic residues in an interval of length $kq$ and the error term depends on $k$. What am I doing wrong here?
Also, how does the correct formula follow from the Pólya-Vinogradov inequality?
 A: Suppose that $q$ is prime.  The Polya-Vinogradov formula states that 
$$\sum_{n=M+1}^{M+N} \chi(n) = O(\sqrt{q} \log q)$$
For quadratic residues, the character being used here is 
$$\chi(n) = \left\{\begin{array}{rl} 1 & \textrm{ if } n \textrm{ is a non-zero quadratic residue} \\ -1 & \textrm{ if } n \textrm{ is a non-zero quadratic non-residue} \\
0 & \textrm{ if } q \textrm{ divides } n \end{array}\right.$$
The key thing here is that a Dirichlet character is $0$ (and not $\pm 1$) on multiples of $q$.  
Suppose now that I look at the interval $[1, kq]$.  If I let $y$ be the number of quadratic residues in this interval which are not multiples of $q$, then the character is equal to $1$ exactly $y$ times, and equal to $0$ exactly $q$ times, so is equal to $-1$ a total of $kq-q-y=k(q-1)-y$ times.  So the character sum is 
$$y - [(k(q-1)-y] = k(q-1)-2y$$
Plugging this into the Polya-Vinogradov formula gives that 
$$y=\frac{q-1}{2} k + O(\sqrt{q \log q})$$
Which is consistent with your observations.  
The difference between what Polya-Vinogradov actually gives you and $\frac{N}{2}$  comes from the handling of places where $\chi(n)=0$.  In practice, usually when Polya-Vinogradov is applied it is for $N$ which is smaller than $q$ (since the character always adds to $0$ on intervals of length $q$ anyway).  Once you restrict down to that size interval, the case where $q|n$ can only change the sum by $1$, so is insignificant.  
