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.

I can't understand what to do in the following example of congruence. I need to decide if this congruence is solvable, and if so, to find all the solutions:$x^2 \equiv 54(77)$.

I need to decide whether $(\frac{54}{77})$=1 or -1.

First of all I want to ask you what is the idea behind Jacobi symbol? Do I use it when I need to decide $(\frac{a}{b})$ and $b$ is not a prime?

both of them are not primes, I want to use Jacobi symbol rules:

$(\frac{54}{77})=(\frac{54}{11})(\frac{54}{7})=(\frac{-1}{77})(\frac{5}{77})=(-1)^{-5}(\frac{-2}{7})=1$. But I know that If the reult is 1 then $54$ may or may not be a quadratic residue $(\mod77)$ . How do I determinate it?

Thanks!

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

Hint: Deal separately with the solutions of $x^2\equiv 54\pmod{7}$ and $x^2\equiv 54\pmod{11}$, and splice solutions together (if there are any) using the Chinese Remainder Theorem.

If there are no solutions mod one of $7$ or $11$, then there are no solutions mod $77$. (Actually, since the Jacobi symbol evaluates to $1$, if there are no solutions mod one of $7$ or $11$, then there are no solutions mod the other.)

Remark: You are right, Jacobi symbol evaluating to $1$ is inconclusive. But the Jacobi symbol is cheap to compute, and if it evaluates to $-1$, then end of story. For small numbers, the Jacobi symbol is not as useful, since if we are interested in $x^2\equiv a \pmod{b}$, factorization of $b$ is easy.

share|improve this answer
    
Let's assume that both $x^2\equiv 54\pmod{7}$ and $x^2\equiv 54\pmod{11}$ are solvable, I know that the Chinese Remainder Theorem is for linear congruences, so how do I use it In this case? Thanks a lot. –  Jozef May 25 '12 at 20:58
    
Well, neither is solvable. But pick a number (not $54$) for which both solvable. Typically the solutions are $x\equiv \pm a \pmod{7}$, $x\equiv \pm b\pmod{11}$. Now pick one combination of the solutions, say $x\equiv a\pmod{7}$, $x\equiv -b\pmod{11}$. This is a CRT problem. Solve it. Do same for other $3$ combinations. [In the general case there are $4$ solutions mod $77$, but not, for example, when we use a number like $44$, which is divisible by $11$, basically because $\pm 0=0$.] –  André Nicolas May 25 '12 at 21:09
    
Added to last comment: So to do the calculations, we need to solve the quadratic congruence mod each of $7$ and $11$ first. Then we end up with (typically) $4$ linear congruence problems. Because of $\pm$ symmetry mod $77$, the CRT work need only be done twice. –  André Nicolas May 25 '12 at 21:18
    
Ok, Let's assume the original congruence was $x \equiv 58( mod 77)$. I end up with two solvable congruences: $x^2 \equiv 2(7)$ and $x^2 \equiv 3(11)$. You're telling me that I need to solve the system of $x \equiv 2(7)$ and $x \equiv -3(11)$? I don't understand why. –  Jozef May 25 '12 at 21:34
1  
That is not what I said. We have $x^2\equiv 2\pmod{7}$. That has the solutions $x\equiv \pm 3\pmod{7}$. The congruence $x^2\equiv 3\pmod{11}$ has the solutions $x\equiv \pm 5\pmod{11}$. Now we need to solve the four systems of congruences (i) $x\equiv 3\pmod{7}$, $x\equiv 5\pmod{11}$; (ii) $x\equiv -3\pmod{7}$, $x\equiv 5\pmod{11}$; (and you know the other two systems). This produces the $4$ solutions mod $77$ of the original congruence. Please let me know if this is clear! –  André Nicolas May 25 '12 at 23:01
show 1 more 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.