3
$\begingroup$

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!

1 Answers 1

5

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.

  • 0
    It is, Thanks a lot Andre.2012-05-26