= Solution
A nonzero residue class $a\pmod p$ is a <quadratic residue> if $a\equiv x^2\pmod p$ for some nonzero $x$. If it is a square, <Fermat's little theorem> gives $a^{(p-1)/2}=x^{p-1}\equiv1$. Conversely, the map $x\mapsto x^2$ on the nonzero classes identifies exactly the pairs $\{x,-x\}$, giving $(p-1)/2$ distinct squares. They are all roots of $X^{(p-1)/2}-1$ over the field $\mathbb F_p$; a <polynomial> of this degree has at most that many roots. Its roots are therefore precisely the squares. This proves <Euler's criterion>
$$
\boxed{a\text{ is a nonzero quadratic residue }\iff a^{(p-1)/2}\equiv1\pmod p}.
$$
Applying it to $-1$ gives $\boxed{(-1/p)=1\iff p\equiv1\pmod4}$. The exclusion of $a=0$ is the usual nonzero-residue convention needed for this equivalence.
For distinct odd <primes> $p,q$, <quadratic reciprocity> states
$$
\boxed{\left(\frac pq\right)\left(\frac qp\right)=(-1)^{(p-1)(q-1)/4}}.
$$
Using the multiplicativity of the <Legendre symbol>, and the supplementary law $(2/p)=(-1)^{(p^2-1)/8}$,
$$
\left(\frac{73}{127}\right)=\left(\frac{127}{73}\right)
=\left(\frac{54}{73}\right)
=\left(\frac2{73}\right)\left(\frac3{73}\right).
$$
The first factor is $1$ because $73\equiv1\pmod8$; the second is $(73/3)=(1/3)=1$ because the reciprocity sign is positive. Thus $\boxed{73\text{ is a quadratic residue modulo }127}$.
Back to article page
