# Verifying quadratic reciprocity for the Jacobi symbol

I am trying to prove:

If $m,n$ are odd coprime positive integers, then $$\Big(\frac mn\Big)\Big(\frac nm\Big)=(-1)^{\large\frac{m-1}2\frac{n-1}2},$$ where $\big(\frac mn\big)$ is the Jacobi symbol.

I already know quadratic reciprocity on odd primes, and I also know that $\big(\frac mn\big)$ is completely multiplicative in both arguments and nonzero iff the arguments are coprime.

How do I show this?

• Cleaned it up to be a proper self-answered question. – Mario Carneiro Jun 19 '15 at 16:33

The proof proceeds by complete induction, first on $n$ and then on $m$ (since the formula is symmetric w.r.t permuting $m$ and $n$, the two inductions are identical). If $m$ is prime, then we are done by regular quadratic reciprocity. If $m=1$, then $\big(\frac 1n\big)=\big(\frac n1\big)=1$ (because $1$ is coprime to $n$, it is not zero, and it is positive because $\big(\frac {1^2}n\big)=\big(\frac 1n\big)^2$), so it reduces to $1\cdot 1=1=(-1)^0$.
Otherwise $m=ab$ for $1<a,b<m$, and by the induction hypothesis $\big(\frac an\big)\big(\frac na\big)=(-1)^{\large\frac{a-1}2\frac{n-1}2}$ and $\big(\frac bn\big)\big(\frac nb\big)=(-1)^{\large\frac{b-1}2\frac{n-1}2}$. Thus:
where in the last step we have $a+b-2\equiv ab-1\pmod 4$ because $(ab-1)-(a+b-2)=(a-1)(b-1)$ which is divisible by $4$ because $a,b$ are odd.