Yesterday, 08:59 PM
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
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
┌────────────────────────────────┐
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘