This law conjectured by Leonhard Euler (1707 – 1783) and first proven by Carl Friedrich Gauss (1777 - 1855).
Let $p > 2$ and $q > 2$ be odd and distinct prime numbers. Then the product of the Legendre symbols has the following explicit formula:
$$\left(\frac{q}{p}\right)\cdot \left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.$$
In particular: * If $p\equiv q\equiv 1 \mod 4,$ then the congruences $x^2(q)\equiv p(q),$ and $x^2(p)\equiv q(p)$ are either both solvable or both not solvable. * If $p\equiv q\equiv 3\mod 4,$ then one of the congruences $x^2(q)\equiv p(q),$ and $x^2(p)\equiv q(p)$ is solvable, the other not solvable.
Proofs: 1
