= Solution
{c}
The <quadratic reciprocity> states that for distinct odd primes $a,b$,
$$
\left(\frac ab\right)\left(\frac ba\right)
=(-1)^{(a-1)(b-1)/4}.
$$
For fixed odd prime $r$, first suppose that $p,q\ne r$. The congruence $p\equiv q\pmod{4r}$ gives the same residues modulo $r$ and modulo four. Reciprocity yields
$$
\left(\frac rp\right)
=\left(\frac pr\right)(-1)^{(r-1)(p-1)/4}
=\left(\frac qr\right)(-1)^{(r-1)(q-1)/4}
=\left(\frac rq\right).
$$
If $p=r$, the congruence forces $r\mid q$, so $q=r$ and both symbols are zero; the same handles $q=r$.
For $n=\prod_jr_j^{a_j}$, where all $r_j$ are odd primes, $4r_j$ divides $4n$. Thus $p\equiv q\pmod{4n}$ implies equality of each prime-numerator <Legendre symbol>. Multiplicativity gives
$$
\boxed{\left(\frac np\right)
=\prod_j\left(\frac{r_j}p\right)^{a_j}
=\prod_j\left(\frac{r_j}q\right)^{a_j}
=\left(\frac nq\right).}
$$
This also covers symbols that vanish; for $n=1$ both sides are one.
Back to article page
