Posted by Jason Polak on 21. July 2018 · Write a comment · Categories: number-theory · Tags: ,

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.

It turns out that the following result is true:

Theorem. For any relatively prime integers $m$ and $n$, the following hold:

  1. If $m$ and $n$ are odd, then $(m/n)(n/m) = (-1)^{(m-1)(n-1)/4}$.
  2. If $m$ is odd and $n$ is even then $(m/n) = 1$ if $n\equiv 2\pmod{4}$ and $(m/n) = (-1)^{(m-1)/2}$ if $n\equiv 0\pmod{4}$.

This theorem is a beautiful result because it can reduce a laborious computation to an utterly simple one. The gist of the proof runs as follows: define $\mu(x,y) = (mx + y,y)$ and $\nu(x,y) = (x, x + ny)$ on $\Z/n\times \Z/m$. By computing the sign of the permutation $\nu\mu^{-1}$ on $\Z/n\times\Z/m$ directly and using the permutation it induces on $\Z/mn\cong\Z/n\times\Z/m$, one arrives at an expression for $(m/n)(n/m)$ that gives the result.

Let's do our example $(3/412871)$. The integer $2\cdot 412870/4$ is odd. Therefore, the theorem tells us that $(3/412871)(412871/3) = -1$. The symbol $(412871/3)$ is easily computed by hand to be $-1$. Therefore, $(3/412871) = 1$. And in case you're the computational algebra type, here's how to check it with Sage:

Enter that command in Sage, and you'll get $1$. Great!

Leave a Reply

Your email address will not be published. Required fields are marked *