+- MKLab (https://mklab.gr)
+-- Forum: [INDEX] (https://mklab.gr/forumdisplay.php?fid=1)
+--- Forum: MATHEMATICS (https://mklab.gr/forumdisplay.php?fid=3)
+---- Forum: ARTICLES (https://mklab.gr/forumdisplay.php?fid=13)
+---- Thread: Euler's criterion (/showthread.php?tid=1388)
Euler's criterion - mklabgr - 07-28-2026
Euler's criterion
Summary
In number theory, Euler's criterion (formulated by Leonhard Euler in 1748) provides a direct method to determine whether an integer $a$ coprime to an odd prime $p$ is a quadratic residue—meaning whether the congruence $x^2 \equiv a \pmod p$ has a integer solution. The criterion states that $a^{(p-1)/2} \equiv 1 \pmod p$ if $a$ is a quadratic residue, and $a^{(p-1)/2} \equiv -1 \pmod p$ if it is a nonresidue, which can be concisely expressed using the Legendre symbol as $\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p$.
Derived from Fermat's Little Theorem and Lagrange's Theorem on polynomial roots, this fundamental result plays a crucial role in modular arithmetic, connects to the law of quadratic reciprocity, and serves as the theoretical backbone for probabilistic primality tests such as the Solovay–Strassen test.
ARTICLE