<s>[INST] Legendre symbols So for odd prime $p$, I have Legendre symbol $(\frac{-1}{p}) = (-1)^{(p-1)/2}$, and let $n\geq 3$ be an odd positive integer.
I have to show that for odd positive integers $n_1$ and $n_2$, we have
$\frac{n_1n_2-1}{2}\equiv \frac{n_1-1}{2} + \frac{n_2-1}{2} \pmod{2}$
And from this I have to deduce $(\frac{-1}{n}) = (-1)^{(n-1)/2}$.

So I have manage to show the first part:
$\frac{n_1n_2-1}{2}\equiv \frac{n_1-1}{2} + \frac{n_2-1}{2} \pmod{2}$
$\frac{n_1n_2-n_1-n_2+1}{2} \equiv 0\pmod{2}$
$\frac{(n_1-1)(n_2-1)}{2} \equiv 0\pmod{2}$
$n_1,n_2$ odd $\implies (n_1-1),(n_2-1)$ even $\implies n_1-1=2a, n_2-1=2b; a,b\in \mathbb{Z}$
$\frac{4ab}{2} \equiv 0\pmod{2}$
$2ab \equiv 0\pmod{2}$
$0 \equiv 0\pmod{2}$
So now, I have to somehow use this to deduce $(\frac{-1}{n}) = (-1)^{(n-1)/2}$, but I have no idea what to do. Any suggestions?
 [/INST] You already know the result when $n$ is prime, so assume that $n$ is composite and positive. Then there exist positive integers $n_1$ and $n_2$ such that $2\le n_1\le n_2<n$ and $n_1 n_2 = n.$ What determines whether a power of $-1$ is $1$ or $-1$ is the exponent modulo $2.$ By what you have already proven, $$(-1)^{\frac{n-1}{2}}=(-1)^{\frac{n_1 n_2 -1}{2}} = (-1)^{\frac{n_1-1}{2}+\frac{n_2-1}{2}}=(-1)^{\frac{n_1-1}{2}}\cdot (-1)^{\frac{n_2-1}{2}}.$$
You can use strong induction on $n,$ so we get $$(-1)^{\frac{n-1}{2}}=\left(\frac{-1}{n_1}\right)\left(\frac{-1}{n_2}\right).$$ This is equal to $\left(\frac{-1}{n}\right)$ by the complete multiplicativity of the Jacobi symbol (in either entry when the other entry is fixed), assuming that is what you are using for $\left(\frac{-1}{n}\right)$ since the Legendre symbol is defined only for primes in the lower entry.
</s>