calculating the Jacobi symbol


To calculate the Jacobi symbolMathworldPlanetmath (am) for positive integers a,m, m odd, we apply the quadratic reciprocity law and the fact that

(am)=(bm)

if abmodm. So if gcd(a,m)=1 (otherwise the Jacobi symbol is 0) and a>m choose bamodm with b<m. Then (am)=(bm). 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=2sc with odd c does the trick since

(bm)=(2m)s(cm).

Using the fact that

(2m)=(-1)m2-18 (1)

we compute (2m) to be 1 if m±1mod8 and -1 if m±3mod8. Now we apply the quadratic reciprocity law:

(cm)=(-1)(c-1)(m-1)4(mc).

The factor (-1)(c-1)(m-1)4 is equal to -1 if c,m3mod4 and 1 if at least one of the numbers c,m is congruentMathworldPlanetmath to 1 modulo 4. At this point we can start thw whole procedure over again for (mc). Eventually we can apply the equation (-1m)=(-1)m-12, which is equal to 1 if m1mod4 and -1 otherwise.

Example: We try to calculate (10723). Since gcd(107,23)=1 and 10715mod23 we find (10723)=(1523). Since both 15 and 23 are congruent 3 modulo 4 we have

(1523)=-(2315)=-(815)=-(215).

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

(10723)=-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 AlgorithmMathworldPlanetmath
Classification msc 11A07
Classification msc 11A15
Classification msc 11Y99