# Solving a non-linear congruence

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}$

-
Do you mean $a,b$ integers? Are you aware that it may have more than $2$ roots it $n$ is not prime? If so, do you seek one or all roots? –  Math Gems Feb 1 '13 at 0:00
en.wikipedia.org/wiki/… –  DanielV Mar 16 at 0:01

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).