Quadratic residue

In number theory, an integer q is a quadratic residue modulo n if it is congruent to a perfect square modulo n; that is, if there exists an integer x such that

${\displaystyle x^{2}\equiv q{\pmod {n}}.}$

Otherwise, q is a quadratic nonresidue modulo n.

Quadratic residues are used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers.