  We estimate the deviation of the number of solutions of the congruence $$
m^2-n^2 \equiv c \pmod q, \qquad 1 \le m \le M, \ 1\le n \le N, $$ from its
expected value on average over $c=1, ..., q$. This estimate is motivated by the
recently established by D. R. Heath-Brown connection between the distibution of
solution to this congruence and the pair correlation problem for the fractional
parts of the quadratic function $\alpha k^2$, $k=1,2,...$ with a real $\alpha$.
