A number

is called a quadratic residue modulo

if there is a positive integer

such that

. The Jacobi symbol

is 0 for numbers

and

with a common factor, 1 if

is a quadratic residue modulo

, and -1 otherwise. The Jacobi symbol reduces to the Legendre symbol if

is an odd prime

.