I learned the following proof from Jean-François Mestre, it is a variant of Zolotarev's.
For every prime number $p>2$, let $T_p\in\mathbf Z[X]$ be the monic polynomial such that $T_p(X+1/X)X^{(p-1)/2}=(X^p-1)/(X-1)=1+X+\dots+X^{p-1}$. The complex roots of $T_p$ are $x+1/x$, where $x$ is a primitive $p$th root of unity. The same holds in any field of characteristic $\neq p$. In a field of characteristic $p$, the only root of $T_p$ is $2$, with multiplicity $(p-1)/2$.
Let $p,q$ be two odd prime numbers, with $p\neq q$.
The resultant $\mathop{\rm Res}(T_p,T_q)$ of $T_p$ and $T_q$ is an integer. Since these polynomials have no common root, this integer is non-zero.
Since these polynomials have no common root in every field, in particular modulo every prime number, this integer is $\pm1$.
Compute this resultant modulo $p$. One gets $\mathop{\rm Res}(T_p,T_q)\equiv T_q(2)^{(p-1)/2}\equiv q^{(p-1)/2}\pmod p$. Consequently, $\mathop{\rm Res}(T_p,T_q)=\left(\frac qp\right)$.
Similarly, $\mathop{\rm Res}(T_q,T_p)=\left(\frac pq\right)$.
Now, $ \mathop{\rm Res}(T_p,T_q) = (-1)^{\deg(T_p)\deg(T_q)} \mathop{\rm Res}(T_q,T_p), $ hence the quadratic reciprocity law.
