# calculating the Jacobi symbol

To calculate the Jacobi symbol  $\left(\frac{a}{m}\right)$ for positive integers $a,m$, $m$ odd, we apply the quadratic reciprocity law and the fact that

 $\left(\frac{a}{m}\right)=\left(\frac{b}{m}\right)$

if $a\equiv b\mod m$. So if $\gcd(a,m)=1$ (otherwise the Jacobi symbol is $0$) and $a>m$ choose $b\equiv a\mod m$ with $b. Then $\left(\frac{a}{m}\right)=\left(\frac{b}{m}\right)$. To apply the quadratic reciprocity law, which basically allows us to exchange $b$ and $m$, we need to make $b$ odd if it is even. Writing $b=2^{s}c$ with odd $c$ does the trick since

 $\left(\frac{b}{m}\right)=\left(\frac{2}{m}\right)^{s}\left(\frac{c}{m}\right).$

Using the fact that

 $\left(\frac{2}{m}\right)=(-1)^{\frac{m^{2}-1}{8}}$ (1)

we compute $\left(\frac{2}{m}\right)$ to be $1$ if $m\equiv\pm 1\mod 8$ and $-1$ if $m\equiv\pm 3\mod 8$. Now we apply the quadratic reciprocity law:

 $\left(\frac{c}{m}\right)=(-1)^{\frac{(c-1)(m-1)}{4}}\left(\frac{m}{c}\right).$

The factor $(-1)^{\frac{(c-1)(m-1)}{4}}$ is equal to $-1$ if $c,m\equiv 3\mod 4$ and $1$ if at least one of the numbers $c,m$ is congruent  to $1$ modulo $4$. At this point we can start thw whole procedure over again for $\left(\frac{m}{c}\right)$. Eventually we can apply the equation $\left(\frac{-1}{m}\right)=(-1)^{\frac{m-1}{2}}$, which is equal to $1$ if $m\equiv 1\mod 4$ and $-1$ otherwise.

Example: We try to calculate $\left(\frac{107}{23}\right)$. Since $\gcd(107,23)=1$ and $107\equiv 15\mod 23$ we find $\left(\frac{107}{23}\right)=\left(\frac{15}{23}\right)$. Since both $15$ and $23$ are congruent $3$ modulo $4$ we have

 $\left(\frac{15}{23}\right)=-\left(\frac{23}{15}\right)=-\left(\frac{8}{15}% \right)=-\left(\frac{2}{15}\right).$

This can be evaluated using equation (1) and we find

 $\left(\frac{107}{23}\right)=-1.$
Title calculating the Jacobi symbol CalculatingTheJacobiSymbol 2013-03-22 14:55:05 2013-03-22 14:55:05 mathwizard (128) mathwizard (128) 4 mathwizard (128) Algorithm  msc 11A07 msc 11A15 msc 11Y99