info prev up next book cdrom email home

Euler's Criterion

For $p$ an Odd Prime and a Positive Integer $a$ which is not a multiple of $p$,

a^{(p-1)/2} \equiv {a\over p}{\rm\ (mod\ } p),

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

See also Quadratic Residue


Rosen, K. H. Ch. 9 in Elementary Number Theory and Its Applications, 3rd ed. Reading, MA: Addison-Wesley, 1993.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 33-37, 1993.

Wagon, S. Mathematica in Action. New York: W. H. Freeman, p. 293, 1991.

© 1996-9 Eric W. Weisstein