## The Jacobi Symbol

Let
$n, \; m$
be odd integers with
$n \gt 3, \; gcd(m, \; n)=1$
. Write
$n=p_1p_2...p_r$
where the
$p_i$
are not necessarily distinct.>br /> The Jacobi symbol is defined as
$(m/n)=(n/p_1)(n/p_2)...(n/p_r)$
where each factor on the right hand side is a Legendre Symbol.
For example,
$(14/275)=(14/5)(14/5)(14/11)=(14/5)(14/5)(3/11)==1 \times 1 \times 1$

since
$1$
is a Quadratic Residue of 5 and
$3 \equiv 25 \; (mod \; 11) \equiv 5^2 \; (mod \; 11)$
so 3 is a quadratic residue of 11.