ℕ

Quadratic Residues

Undergraduate

Definition

An integer a is a quadratic residue mod n if there exists x such that x² ≡ a (mod n).

((a)/(p)) = \begincases 1 & QR \\ -1 & QNR \\ 0 & p|a \endcases

Legendre symbol

((a)/(p)) ≡ a^(p-1)/2 ±odp

Euler's criterion

((-1)/(p)) = (-1)^(p-1)/2

Condition for -1 being QR

Example 1

Find all quadratic residues mod 7.

Example 2

Is 3 a quadratic residue mod 11?

Square root computation, zero-knowledge

Quadratic reciprocity

Solovay-Strassen test