Compute the Jacobi symbol $\left(\frac{47}{109}\right)$ using multiplicativity and quadratic reciprocity


So this means $\left(\frac{47}{109}\right)$ and $\left(\frac{109}{47}\right)=\left(\frac{15}{47}\right)$ have the same signs, and

$\left(\frac{15}{47}\right)\left(\frac{47}{15}\right)=(-1)^{7\cdot13}=-1$ have different signs so, $\left(\frac{15}{47}\right)=-\left(\frac{47}{15}\right)=-\left(\frac{2}{15}\right)$

now since $(2,3)=1$ and $(2,5)=1$ we have


Using Euler's criterion or Eisenstein's lemma I found that the result is $-1$, but how can I show that $\left(\frac{2}{3}\right)$ and $\left(\frac{2}{5}\right)$ have the same sign ?

(which means that, $x^2\equiv2\mod5$ is solvable $\iff x^2\equiv2\mod3$ is solvable)


You can just compute it --- $2$ is not a quadratic residue modulo either $3$ or $5$, so neither equation is solvable (both Legendre symbols are $-1$).

For the first part, while you did it correctly, it's easier to recognize that, for example, $47\equiv 3\mod 4$ and $109\equiv 1\mod 4$ so that $\left(\frac{47}{109}\right) = \left(\frac{109}{47}\right)$ rather than computing the appropriate power of $-1$.

  • $\begingroup$ I think I got it, for every odd, positive integer $n$: $\left(\frac{2}{n}\right)=(-1)^{\frac{n^2-1}{8}}$, but why do you take $\mod 4$ ? $\endgroup$ – derivative Mar 15 '15 at 13:45
  • $\begingroup$ Yes, that is true. $\endgroup$ – rogerl Mar 15 '15 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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