Euler's Criterion

Euler's criterion helps determine whether a number \(a\) is a quadratic residue modulo a prime \(p\)—meaning whether there exists some number \(x\) such that \(x^2 \equiv a \pmod{p}\). The criterion states that for an odd prime \(p\) and an integer \(a\) that is coprime to \(p\), \(a\) is a quadratic residue mod \(p\) if and only if \(a^{(p-1)/2} \equiv 1 \pmod{p}\). If the result is \(-1\), then \(a\) is a non-residue, meaning no such \(x\) exists. It provides a straightforward test for quadratic residue status.