Solving a non-linear congruence

Question

How can we solve for $x$, knowing the integer $n$ and the real numbers $a$ and $b$, the following non-linear congruence:

$(x+a)^2=-b\pmod{n}$

Specifically in this example:

$(x+\frac{1}{2})^2=-\frac{3}{4}\pmod{n}$

Answer 1

If $a$ and $b$ are really any real numbers and you want to work in the ring $\mathbb R /n \mathbb Z$, then I cannot help you.

If instead, as in your example $x^2 + x + 1 = 0 [n]$ you have a quadratic polynomial with coefficients in $\mathbb Z/n \mathbb Z$ and you want to find the solutions inside this ring, then I have a method.

Decompose $n$ in a product of primes $n = p_1^{m_1}... p_q^{m_q}$. Then solve each equation modulo $p_i^{m_i}$, say there are $N(p_i^{m_i})$ solutions. Then your equation modulo $n$ has $N(p_1^{m_1})N(p_2^{m_2})...N(p_q^{m_q})$ solutions.

Another thing is that if $m_i = 1$ then, modulo $p_i$ there is either 2 solution or 0, if $\Delta$ is a square mod $p_i$ or not (and to know this, you can calculate the Legendre symbol).