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
    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.2012-05-25
  • 0
    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$.]2012-05-25
  • 0
    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.2012-05-25
  • 0
    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.2012-05-25
  • 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!2012-05-25
  • 0
    It is, Thanks a lot Andre.2012-05-26