info prev up next book cdrom email home

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

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

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

\begin{displaymath}
(b/p)=(-1)^t,
\end{displaymath}

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.




© 1996-9 Eric W. Weisstein
1999-05-25