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 bmodm$. So if $\gcd (a,m)=1$ (otherwise the Jacobi symbol is $0$) and $a>m$ choose $b\equiv amodm$ with . 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 1mod8$ and $-1$ if $m\equiv \pm 3mod8$. 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 3mod4$ 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 1mod4$ and $-1$ otherwise.

Example: We try to calculate $\left(\frac{107}{23}\right)$. Since $\gcd (107,23)=1$ and $107\equiv 15mod23$ 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
Canonical name	CalculatingTheJacobiSymbol
Date of creation	2013-03-22 14:55:05
Last modified on	2013-03-22 14:55:05
Owner	mathwizard (128)
Last modified by	mathwizard (128)
Numerical id	4
Author	mathwizard (128)
Entry type	Algorithm
Classification	msc 11A07
Classification	msc 11A15
Classification	msc 11Y99