Gauss's Criterion

Let $p$ be an Odd Prime and $b$ a Positive Integer not divisible by $p$. Then for each Positive Odd Integer $2k-1< p$, let $r_k$ be

$$r_k\equiv (2k-1)b\ \left({{\rm mod\ } {p}}\right)$$

with $0<r_k<p$, and let $t$ be the number of Even $r_k$s. Then

$$(b/p)=(-1)^t,$$

where $(b/p)$ is the Legendre Symbol.

References

Shanks, D. ``Gauss's Criterion.'' §1.17 in Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 38-40, 1993.