Z. Rudnick and P. Sarnak have proved that the pair correlation for the
fractional parts of $n^2 \alpha$ is Poissonian for almost all $\alpha$.
However, they were not able to find a specific $\alpha$ for which it holds. We
show that the problem is related to the problem of determining the number of
$(a,b,r) \in \N^3$ such that $a \le M$, $b \le N$, $r \le K$ and $p ab \equiv r
(q)$ for $p$ and $q$ coprime. With suitable assumptions on the relative size of
$K$, $M$, $N$ and $q$ one should expect there to be $KMN/q$ such triples
asymptotically and we will show that this holds on average.