
Here we would show a beautiful application of Fermat’s Little Theorem.
An integer is a quadratic residue with respect to prime
if
for some integer
.
Given a prime and an integer
, how fast can we decide whether
is a quadratic residue modulo
? As it turns out (courtesy to Euler), pretty fast.