Quadratic reciprocity

Statement

If $p,q$ are distinct odd prime numbers, then:

$\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}}$

where $\left({\frac {p}{q}}\right)$ and $\left({\frac {q}{p}}\right)$ are the respective Legendre symbols: a Legendre symbol takes the value $+1$ if the top value is a quadratic residue modulo the bottom value, and $-1$ if the top value is a quadratic nonresidue modulo the bottom value.

The statement can also be captured using the following cases for the residue classes of $p$ and $q$ modulo $4$:

Congruence class of $p$ mod $4$	Congruence class of $q$ mod $4$	Both quadratic residues mod each other?	Both quadratic nonresidues mod each other?	$p$ quadratic nonresidue mod $q$, $q$ quadratic residue mod $p$?	$p$ quadratic residue mod $q$, $q$ quadratic nonresidue mod $p$?
1	1	Possible (example: 5, 29)	Possible (example: 5, 13)	Impossible	Impossible
1	-1	Possible (example: 5, 19)	Possible (example: 5, 7)	Impossible	Impossible
-1	1	Possible (example: 19, 5)	Possible (example: 7, 5)	Impossible	Impossible
-1	-1	Impossible	Impossible	Possible (example: 3,7)	Possible (example: 7, 3)