Quadratic residue

In modular arithmetic, a quadratic residue for the modulus N is a number which can be expressed as the residue of a² modulo N for some integer a. A quadratic non-residue of N is a number which is not a quadratic residue of N.

Legendre symbol

When the modulus is a prime p, the Legendre symbol $\left({\frac {a}{p}}\right)$ expresses the quadratic nature of a modulo p. We write

$\left({\frac {a}{p}}\right)=0\,$ if p divides a;

$\left({\frac {a}{p}}\right)=+1\,$ if a is a quadratic residue of p;

$\left({\frac {a}{p}}\right)=-1\,$ if a is a quadratic non-residue of p.

The Legendre symbol is multiplicative, that is,

$\left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right).\,$

Jacobi symbol

For an odd positive n, the Jacobi symbol $\left({\frac {a}{n}}\right)$ is defined as a product of Legendre symbols

$\left({\frac {a}{n}}\right)=\prod _{i=1}^{r}\left({\frac {a}{p_{i}}}\right)^{e_{i}}\,$

where the prime factorisation of n is

$n=\prod _{i=1}^{r}{p_{i}}^{e_{i}}.\,$

The Jacobi symbol is bimultiplicative, that is,

$\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right)\,$

and

$\left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right).\,$

If a is a quadratic residue of n then the Jacobi symbol $\left({\frac {a}{n}}\right)=+1$, but the converse does not hold. For example,

$\left({\frac {3}{35}}\right)=\left({\frac {3}{5}}\right)\left({\frac {3}{7}}\right)=(-1)(-1)=+1,\,$

but since the Legendre symbol $\left({\frac {3}{5}}\right)=-1$, it follows that 3 is a quadratic non-residue of 5 and hence of 35.

See also

• Quadratic reciprocity

References

• G. H. Hardy; E. M. Wright (2008). An Introduction to the Theory of Numbers, 6th ed. Oxford University Press. ISBN 0-19-921986-9.