Formula for the root of $x^2=-3\mod n$ when $n=p_1^{k_1}\cdots p_l^{k_l}$ and $p_i$ primes equal to $1\mod 3$

43 Views Asked by At

Consider the equation $$x^2=-3\mod n,$$ where $n=p_1^{k_1}\cdots p_l^{k_l}$ with $p_i$ primes equal to $1\mod 3$. Notice that any such $n$ can written as $a^2+3b^2$ (by a theorem of Fermat) for some integers $a,b$ such that exactly one is odd.

My question: does there exist a general formula for the roots to this equation in terms of $n$?

What I have in mind is best illustrated by the following example. Consider the case $a=1$, $b=2c$. In this case, $$n=1+12c^2,$$ and a root to the equation is then given by $$x=6c.$$ My question then is whether for more general $n=a^2+3b^2$ there exists an expression for a root $x$ in terms of $a$ and $b$.