# Computing Jacobi symbol $\left(\frac{47}{109}\right)$

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

$\left(\frac{47}{109}\right)\left(\frac{109}{47}\right)=(-1)^{\frac{47-1}{2}\frac{109-1}{2}}=(-1)^{23\cdot54}=1$

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

$-\left(\frac{2}{15}\right)=-\left(\frac{2}{3}\right)\left(\frac{2}{5}\right)$

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$.
• 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$ ? – derivative Mar 15 '15 at 13:45