Euler's criterion
let be and odd prime and
Euler's criterion can be concisely reformulated using the Legendre symbol
Proof.
from Fermat's Little Theorem which can be written as
Therefore either
or
Case one: ( is a quadratic residue) let we a primitive root of as is a quadratic residue for some
this proves that
Case two: ( is a quadratic non-residue) for some as is a quadratic non-residue
lets assume
Which contradicts is a primitive root of Therefore
□