= Solution
The <quadratic reciprocity>[quadratic reciprocity law] states that distinct odd primes $a,b$ satisfy
$$
\left(\frac ab\right)\left(\frac ba\right)=(-1)^{((a-1)/2)((b-1)/2)}.
$$
First suppose $p\ne q$. If the odd prime $r$ equalled one of them, divisibility of $p-q$ by $r$ would force the other to equal $r$ too, a contradiction. Thus reciprocity applies to $r,p$ and $r,q$. The <modular congruence> modulo $4r$ gives both $p\equiv q\pmod r$ and $p\equiv q\pmod4$. Therefore $(p/r)=(q/r)$, and the reciprocity signs are identical. Rearranging the two reciprocity identities proves $\boxed{(r/p)=(r/q)}$. If $p=q$, the equality is immediate, including a zero <Legendre symbol> when $p=r$.
For general odd $n>1$, factor $n=\prod_jr_j^{e_j}$. If $p=q$ there is nothing to prove. Otherwise neither $p$ nor $q$ divides $n$, since any such divisor, together with $4n\mid p-q$, would force $p=q$. Each $4r_j$ divides $p-q$, so the first result and multiplicativity of the <Legendre symbol> give
$$
\left(\frac np\right)=\prod_j\left(\frac{r_j}p\right)^{e_j}
=\prod_j\left(\frac{r_j}q\right)^{e_j}
=\boxed{\left(\frac nq\right)}.
$$
For $n=1$, both symbols equal one.
Back to article page
