Euler’s Criterion for Quadratic Residues

Leonhard Euler (source: Prolineserver)

Here we would show a beautiful application of Fermat’s Little Theorem.

An integer a is a quadratic residue with respect to prime p if a \equiv x^2 \mod{p} for some integer x.

Given a prime p and an integer a, how fast can we decide whether a is a quadratic residue modulo p? As it turns out (courtesy to Euler), pretty fast.

Continue reading “Euler’s Criterion for Quadratic Residues”