\[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.