<s>[INST] A question on Brahmagupta Identity The Brahmagupta Identity states that
$$
\begin{align}
N & = (a^2+nb^2 )(c^2+nd^2 ) \\
  & = (ac-nbd)^2+n(ad+bc)^2 \\
  & = (ac+nbd)^2+n(ad-bc)^2 \\
\end{align}
$$
Knowing only $N$, is there a way to find $n$ such that the two cofactors of $N$ (not necessarily prime) can each be represented in the form $x^2 + ny^2$.
Any $n$ that is a solution must satisfy the condition
$$
\begin{align}
N & \equiv (ac + nbd)^2  & \mod {n} \\
  & \equiv k^2 & \mod {n}
\end{align}
$$
i.e., $N$ is a quadratic residue modulo $n$.
Also,
$$
\begin{align}
N & \equiv (ac + bd)^2 + (ad - bc)^2  & \mod {(n-1)} \\
  & \equiv u^2 + v^2 & \mod {(n-1)}
\end{align}
$$
i.e., $N$ must be the sum of two quadratic residues modulo $n-1$.
Assuming, the factorization of $N$ is unknown,
Q1: Are there any other conditions that can help with finding such candidate $n$ efficiently (and eliminating ones that are not fit)?
Q2: Does an $n$ always exist for all $N$ or are there any obstructions?
 [/INST] $N=35$   is represented as $x^2 + n y^2 $   for
$$  n = 10, 19,  26, 31, 34, 35  \; .  $$
In particular, it is not represented by $x^2 + y^2, x^2 + 2 y^2, x^2 + 3 y^2, x^2 + 4 y^2, x^2 + 5 y^2$
For any of the $n$ above, $5,7$   are not represented by $x^2 + n y^2 $
Same idea for $$N = 55583= 11 \cdot 31   \cdot 163  $$
which is represented as $x^2 + n y^2 $ for
$$  n =       358, \;  827, \;  1294, \; 1759, \; 2222, \; 2683, \ldots  $$
but for no smaller $n.$
</s>