ABSTRACT

We say that a number a is a square mod n if x2 ≡ a (mod n) has a solution. For example, 2 is a square mod 7 since 32 ≡ 2 (mod 7), and −1 is a square mod 5 since 22 ≡ −1 (mod 5). However, 2 is not a square mod 3 because x2 6≡ 2 (mod 3) for x = 0, 1, 2. If a is a square mod n, we say that a is a quadratic residue mod n. If not, a is a quadratic nonresidue.