Equations of this type, for $n$ prime, have been studied by 
Christian Elsholtz in <A HREF="http://www.math.tugraz.at/~elsholtz/WWW/papers/papers30nathanson-new-address3.pdf">A combinatorial approach to sums of two squares and related problems</A>

> In this paper we study elementary approaches to classical theorems on
> representations of primes of the form $ax^2 + by^2$, in particular the
> two squares theorem. While most approaches make use of quadratic
> residues, we study a route initiated by Liouville, and simplified by
> Heath-Brown and Zagier.

<IMG SRC="http://ilorentz.org/beenakker/MO/sumofsquares.png"/>