Evaluating Jacobi Symbols and Proof

Question

How do I evaluate the following Jacobi Symbols?

1. $(-79/105)$
2. $(87/133)$
3. $(91/129)$

Also, what is the proof that if $a$ is a quadratic residue $\mod n$, then $(a/n)=1$, but not conversely?

Answer 1

Just use this: http://en.wikipedia.org/wiki/Law_of_quadratic_reciprocity and factorisation theorem. $\left( \frac{91}{129} \right)=\left( \frac{7}{129} \right) \left( \frac{13}{129} \right)=\left( \frac{129}{7} \right)(-1)^{3*64} \left( \frac{129}{13} \right) (-1)^{6*64}=\left( \frac{3}{7} \right) \left( \frac{43}{7} \right) \left( \frac{3}{13} \right) \left( \frac{43}{13} \right) = \ldots$

If $a$ is a quadratic residue then there is $b \in \mathbb{Z}_n$ such that $a\equiv b^2 \pmod{n}$. Therefore $\left( \frac{a}{n} \right) = \left( \frac{b^2}{n} \right) = \left( \frac{b}{n} \right)^2=1$

The converse doesn't hold. Take for example $a=2 \; \; n=15$. Hence

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

but $2$ can't be a quadratic residue $\pmod{15}$, since it's not $\pmod{3}$.