Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.