PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] calculating the Jacobi symbol (Algorithm)

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

$\displaystyle \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<m$. 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^sc$ with odd $ c$ does the trick since
$\displaystyle \left(\frac{b}{m}\right)=\left(\frac{2}{m}\right)^s\left(\frac{c}{m}\right).$
Using the fact that
$\displaystyle \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:
$\displaystyle \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\equiv15\mod23$ we find $ \left(\frac{107}{23}\right)=\left(\frac{15}{23}\right)$. Since both $ 15$ and $ 23$ are congruent $ 3$ modulo $ 4$ we have

$\displaystyle \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
$\displaystyle \left(\frac{107}{23}\right)=-1.$



"calculating the Jacobi symbol" is owned by mathwizard.
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: equation, eventually, point, congruent, numbers, factor, even, quadratic reciprocity, odd, integers, positive, Jacobi symbol, calculate

This is version 1 of calculating the Jacobi symbol, born on 2004-12-29.
Object id is 6604, canonical name is CalculatingTheJacobiSymbol.
Accessed 2327 times total.

Classification:
AMS MSC: 11A07 (Number theory :: Elementary number theory :: Congruences; primitive roots; residue systems)
 11A15 (Number theory :: Elementary number theory :: Power residues, reciprocity)
 11Y99 (Number theory :: Computational number theory :: Miscellaneous)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)