Equations of this type, for $n$ prime, have been studied by Christian Elsholtz in A combinatorial approach to sums of two squares and related problems
http://ilorentz.org/beenakker/MO/sumofsquares.pngIn 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.
