The law of quadratic reciprocity for Jacobi symbols says if m and n are positive coprimes intergers then:
$\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\tfrac{m-1}{2}\cdot\tfrac{n-1}{2}} = \begin{cases} 1 & \text{if } n \equiv 1 \pmod 4 \text{ or } m \equiv 1 \pmod 4,\\ -1 & \text{if } n\equiv m \equiv 3 \pmod 4 \end{cases}$
In all implementations of calculating the Jacobi symbol I've seen, they just seems to ignore this coprime requirement and just turn flip the symbol.
Some examples that show this:
- http://primes.utm.edu/glossary/page.php?sort=JacobiSymbol
- http://math.fau.edu/richman/jacobi.htm
- http://2000clicks.com/MathHelp/NumberTh27JacobiSymbolAlgorithm.aspx
- http://www.planetmath.org/CalculatingTheJacobiSymbol
Why can this coprime requirement be ignored?
When implementing this, checking that the gcd would clearly slow it down.