If $m$ and $n$ are relatively prime integers, the Jacobi symbol $(m/n)$ is defined as the sign of the permutation $x\mapsto mx$ on the set $\Z/n$. Let's give a simple example: $(7/5)$. The permutation on $\{1,2,3,4\}$ is given by $(1 2 4 3) = (1 2)(2 4)(4 3)$ which has an odd number of transpositions. Therefore, $(7/5) = -1$.

Note that as in this example, it is sufficient to compute the sign of the permutation on $\Z/n – \{0\}$, since multiplication always leaves zero fixed.

But what if we wanted to compute something like $(3/412871)$? These numbers aren't so big, so a computer could do it directly. However, there is a better way to do the computation of the Jacobi symbol $(m/n)$ if one of $m$ or $n$ is much larger than the other one. This method is good for computers too when one of the numbers is *so* large, that a direct computation even by a fast computer would be hopeless.

More »