User:James in dc/sandbox/Jacobi symbol

sandbox

Jacobi symbol

In algebraic number theory and related branches of mathematics the Jacobi symbol $\left({\tfrac {a}{m}}\right)$ is defined for all integers $a$ and all positive odd integers $m.$. For $m=p_{1}p_{2}\dots$ where the $p_{i}$ are odd primes the Jacobi symbol is the product of Legendre symbols

$\left({\frac {a}{m}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)\dots$. (and for completeness $\left({\frac {a}{1}}\right)$ is defined to be $1.$)

Properties of the Jacobi symbol

The Legendre symbol $\left({\tfrac {a}{p}}\right)$ is defined for all integers $a$ and all odd primes $p$ by

$\left({\frac {a}{p}}\right)=\left\{{\begin{array}{rl}0&{\text{if }}a\equiv 0{\pmod {p}},\\1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x\colon \;a\equiv x^{2}{\pmod {p}},\\-1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and there is no such }}x.\end{array}}\right.$

The properties of the Jacobi symbol are derived from those of the Legendre symbol.

Since $\left({\tfrac {a_{1}a_{2}}{p}}\right)=\left({\tfrac {a_{1}}{p}}\right)\left({\tfrac {a_{2}}{p}}\right)$ is true for each factor, $\left({\tfrac {a_{1}a_{2}}{m}}\right)=\left({\tfrac {a_{1}}{m}}\right)\left({\tfrac {a_{2}}{m}}\right).$

Obviously from the definition $\left({\tfrac {a}{m_{1}m_{2}}}\right)=\left({\tfrac {a}{m_{1}}}\right)\left({\tfrac {a}{m_{2}}}\right).$

These imply that $\left({\tfrac {ab^{2}}{m}}\right)=\left({\tfrac {a}{m}}\right)$ and $\left({\tfrac {a}{mn^{2}}}\right)=\left({\tfrac {a}{m}}\right).$

If $a_{1}\equiv a_{2}{\pmod {m}}$ then $a_{1}\equiv a_{2}{\pmod {p}}$ for every $p$ in the product so $\left({\tfrac {a_{1}}{p}}\right)=\left({\tfrac {a_{2}}{p}}\right)$ and therefore $\left({\tfrac {a_{1}}{m}}\right)=\left({\tfrac {a_{2}}{m}}\right).$

If $\gcd(a,m)>1$ then one of the $p$s divides $a,\;$ $\left({\tfrac {a}{p}}\right)=0$ and $\left({\tfrac {a}{m}}\right)=0.$

If $\gcd(a,m)=1$ then every $\left({\tfrac {a}{p}}\right)=\pm 1$ and $\left({\tfrac {a}{m}}\right)=\pm 1$ as well.

Differences between Legendre and Jacobi symbols

$\left({\tfrac {a}{m}}\right)=1$ for composite $m$ only means that there were an even number of minus signs in the product; it does not mean that $a$ is a quadratic residue ${\bmod {m}}$. For prime $m$ it does.

Euler's criterion is not true for composite $m$. For example $\left({\tfrac {2}{15}}\right)=1$ but $2^{7}\equiv 8{\pmod {15}}.$ See uses, below.

Quadratic reciprocity

First Supplement

Let $m=p_{1}p_{2}\cdots q_{1}q_{2}\dots$ where $p_{i}\equiv 1{\pmod {4}}$ and $q_{i}\equiv 3{\pmod {4}}$. The values of the Legendre symbols are known: $\left({\tfrac {-1}{p}}\right)=1$ and $\left({\tfrac {-1}{q}}\right)=-1.$

$m\equiv 3{\pmod {4}}$ if and only if the number of $q_{i}$ is odd.

Likewise $\left({\tfrac {-1}{m}}\right)=\left({\tfrac {-1}{p_{1}}}\right)\left({\tfrac {-1}{p_{2}}}\right)\cdots \left({\tfrac {-1}{q_{1}}}\right)\left({\tfrac {-1}{q_{2}}}\right)\dots$ is $-1$ if and only if the number of $q_{i}$ is odd. This shows that

$\left({\frac {-1}{m}}\right)={\begin{cases}1&{\text{if }}m\equiv 1{\pmod {4}}\\-1&{\text{if }}m\equiv 3{\pmod {4}}\end{cases}}$

which is equivalent to

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

Second Supplement

Let $m=p_{1}p_{2}\cdots q_{1}q_{2}\dots$ where $p_{i}\equiv \pm 1{\pmod {8}}$ and $q_{i}\equiv \pm 3{\pmod {8}}$. The values of the Legendre symbols are known: $\left({\tfrac {2}{p}}\right)=1$ and $\left({\tfrac {2}{q}}\right)=-1.$

$m\equiv \pm 3{\pmod {8}}$ if and only if the number of $q_{i}$ is odd.

Likewise $\left({\tfrac {2}{m}}\right)=\left({\tfrac {2}{p_{1}}}\right)\left({\tfrac {2}{p_{2}}}\right)\cdots \left({\tfrac {2}{q_{1}}}\right)\left({\tfrac {2}{q_{2}}}\right)\dots$ is $-1$ if and only if the number of $q_{i}$ is odd. This shows that

$\left({\frac {2}{m}}\right)={\begin{cases}1&{\text{if }}m\equiv 1,7\;\;\equiv 0\pm 1{\pmod {8}}\\-1&{\text{if }}m\equiv 3,5\;\;\equiv 4\pm 1{\pmod {8}}\end{cases}}$

which is equivalent to

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

Combining with the first supplement gives

$\left({\frac {-2}{m}}\right)={\begin{cases}1&{\text{if }}m\equiv 1,3\;\;\equiv 2\pm 1{\pmod {8}}\\-1&{\text{if }}m\equiv 5,7\;\;\equiv 6\pm 1{\pmod {8}}\end{cases}}$

which is equivalent to

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

Legendre

$a$ must be positive and odd.

Let $m=p_{1}p_{2}\cdots q_{1}q_{2}\cdots$ where $p_{i}\equiv 1{\pmod {4}}$ and $q_{i}\equiv 3{\pmod {4}}$.

In the same way let $a=b_{1}b_{2}\cdots c_{1}c_{2}\cdots$ where the $b_{i}$ and $c_{i}$ are prime and $b_{i}\equiv 1{\pmod {4}}$ and $c_{i}\equiv 3{\pmod {4}}$.

The values of the inverted Legendre symbols are known: $\left({\tfrac {b}{p}}\right)=\left({\tfrac {p}{b}}\right),\;\left({\tfrac {c}{p}}\right)=\left({\tfrac {p}{c}}\right),\;\left({\tfrac {b}{q}}\right)=\left({\tfrac {q}{b}}\right),\;\left({\tfrac {c}{q}}\right)=-\left({\tfrac {q}{c}}\right)$

$m\equiv 3{\pmod {4}}$ if and only if the number of $q_{i}$ is odd

$a\equiv 3{\pmod {4}}$ if and only if the number of $c_{i}$ is odd.

${\begin{aligned}\left({\frac {a}{m}}\right)&=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)\cdots \left({\frac {a}{q_{1}}}\right)\left({\frac {a}{q_{2}}}\right)\dots \\&=\left({\frac {b_{1}\cdots c_{1}\cdots }{p_{1}}}\right)\left({\frac {b_{1}\cdots c_{1}\cdots }{p_{2}}}\right)\cdots \left({\frac {b_{1}\cdots c_{1}\cdots }{q_{1}}}\right)\dots \\&=\left({\frac {b_{1}}{p_{1}}}\right)\cdots \left({\frac {c_{1}}{p_{1}}}\right)\cdots \left({\frac {b_{1}}{p_{2}}}\right)\cdots \left({\frac {c_{1}}{p_{2}}}\right)\cdots \left({\frac {b_{1}}{q_{1}}}\right)\cdots \left({\frac {c_{1}}{q_{1}}}\right)\dots \\&=\pm \left({\frac {p_{1}}{b_{1}}}\right)\cdots \left({\frac {p_{1}}{c_{1}}}\right)\cdots \left({\frac {p_{2}}{b_{1}}}\right)\cdots \left({\frac {p_{2}}{c_{1}}}\right)\cdots \left({\frac {q_{1}}{b_{1}}}\right)\cdots \left({\frac {q_{1}}{c_{1}}}\right)\dots \\&=\pm \left({\frac {p_{1}}{b_{1}}}\right)\left({\frac {p_{2}}{b_{1}}}\right)\cdots \left({\frac {q_{1}}{b_{1}}}\right)\cdots \left({\frac {p_{1}}{b_{2}}}\right)\left({\frac {p_{2}}{b_{2}}}\right)\cdots \left({\frac {q_{1}}{b_{2}}}\right)\dots \\&=\pm \left({\frac {p_{1}p_{2}\cdots q_{1}\cdots }{b_{1}}}\right)\left({\frac {p_{1}p_{2}\cdots q_{1}\cdots }{b_{2}}}\right)\cdots \left({\frac {p_{1}p_{2}\cdots q_{1}\cdots }{c_{1}}}\right)\dots \\&=\pm \left({\frac {m}{b_{1}}}\right)\left({\frac {m}{b_{2}}}\right)\cdots \left({\frac {m}{c_{1}}}\right)\dots \\&=\pm \left({\frac {m}{a}}\right).\end{aligned}}$

The sign is negative if and only if the number of $c_{i}q_{j}$ factors is odd, i.e. when both the number of $q_{i}$ is odd and the number of $c_{j}$ is odd. This shows that

$\left({\frac {a}{m}}\right)={\begin{cases}\;\;\;\left({\frac {m}{a}}\right)&{\text{if }}m\equiv 1{\pmod {4}}{\text{ or }}a\equiv 1{\pmod {4}}\\-\left({\frac {m}{a}}\right)&{\text{if }}m\equiv 3{\pmod {4}}{\text{ and }}a\equiv 3{\pmod {4}}\end{cases}}$

which is equivalent to

$\left({\frac {a}{m}}\right)=\left({\frac {m}{a}}\right)(-1)^{{\tfrac {m-1}{2}}{\tfrac {a-1}{2}}}.$

Gauss

$a$ must be positive and odd.

Define the $^{*}$ operator on positive odd $m$ as:

$m^{*}={\begin{cases}\;\;\;m&{\text{if }}m\equiv 1{\pmod {4}}\\-m&{\text{if }}m\equiv 3{\pmod {4}}.\end{cases}}$

This operator is multiplicative $(ab)^{*}=a^{*}b^{*}.$

Let $m=p_{1}p_{2}\cdots$ and $a=b_{1}b_{2}\cdots$.

For every Legendre symbol in the product it is known that $\left({\tfrac {b}{p}}\right)=\left({\tfrac {p^{*}}{b}}\right).$

${\begin{aligned}\left({\frac {a}{m}}\right)&=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)\cdots \\&=\left({\frac {b_{1}b_{2}\cdots }{p_{1}}}\right)\left({\frac {b_{1}b_{2}\cdots }{p_{2}}}\right)\cdots \\&=\left({\frac {b_{1}}{p_{1}}}\right)\left({\frac {b_{2}}{p_{1}}}\right)\cdots \left({\frac {b_{1}}{p_{2}}}\right)\left({\frac {b_{2}}{p_{2}}}\right)\cdots \\&=\left({\frac {p_{1}^{*}}{b_{1}}}\right)\left({\frac {p_{1}^{*}}{b_{2}}}\right)\cdots \left({\frac {p_{2}^{*}}{b_{1}}}\right)\left({\frac {p_{2}^{*}}{b_{2}}}\right)\cdots \\&=\left({\frac {p_{1}^{*}}{b_{1}}}\right)\left({\frac {p_{2}^{*}}{b_{1}}}\right)\cdots \left({\frac {p_{1}^{*}}{b_{2}}}\right)\left({\frac {p_{2}^{*}}{b_{2}}}\right)\cdots \\&=\left({\frac {p_{1}^{*}p_{2}^{*}\cdots }{b_{1}}}\right)\left({\frac {p_{1}^{*}p_{2}^{*}\cdots }{b_{2}}}\right)\cdots \\&=\left({\frac {m^{*}}{b_{1}}}\right)\left({\frac {m^{*}}{b_{2}}}\right)\cdots \\&=\left({\frac {m^{*}}{a}}\right).\end{aligned}}$

Gauss' lemma

Gauss's lemma extends to Jacobi symbols. Let $m>0$ be an odd number and define the sets $I=\{i:1\leq i\leq {\tfrac {m-1}{2}}\}$ and $-I=\{-j:j\in I\}$ Then $(\mathbb {Z} /m\mathbb {Z} )=I\cup -I\cup \{0\}$. For $a\in I,\gcd(a,m)=1$ let $t=\#\{j\in I:aj\in -I\}$.

Then $\left({\frac {a}{m}}\right)=(-1)^{t}$.

Zolotarev's lemma

Zolotarev's lemma extends to Jacobi symbols. For $a\in (\mathbb {Z} /m\mathbb {Z} )^{\times }$ let $\pi _{a}$ be the permutation of the set $(\mathbb {Z} /m\mathbb {Z} )$ (all residue classes, not just the relatively prime ones) induced by multiplication by $a$. The signature of this permutation is the Jacobi symbol:

$\left({\frac {a}{m}}\right)=\varepsilon (\pi _{a})$

See here for details and an example.

Calculating the Jacobi symbol

The expression $a{\bmod {b}}$ means any number $x$ satisfying $x\equiv a{\pmod {b}}$ and $|x|<|b|.$

Repeat these steps until $a$ is 0 or 1. If it is 0, the two original numbers were not relatively prime; if it is 1 the accumulated sign is the value of the Jacobi symbol.

1) if $a$ is negative $\left({\tfrac {a}{m}}\right)=\left({\tfrac {-1}{m}}\right)\left({\tfrac {|a|}{m}}\right)$       I.e. flip the sign if $m\equiv 3{\pmod {4}}$.

2) If $a$ is even repeatedly divide by 4 until $a$ is odd or is twice an odd number.

In the latter case $\left({\tfrac {2a}{m}}\right)=\left({\tfrac {2}{m}}\right)\left({\tfrac {a}{m}}\right)$       I.e. flip the sign if $m\equiv \pm 3{\pmod {8}}$.

3) If $a$ is odd and positive $\left({\tfrac {a}{m}}\right)=(-1)^{{\tfrac {m-1}{2}}{\tfrac {a-1}{2}}}\left({\tfrac {m{\bmod {a}}}{a}}\right)$       I.e. flip the sign if $m\equiv 3{\pmod {4}}$ and $a\equiv 3{\pmod {4}}$.

A few examples:

$\left({\tfrac {-24}{5}}\right)=\left({\tfrac {-1}{5}}\right)\left({\tfrac {24}{5}}\right)=\left({\tfrac {24}{5}}\right)=\left({\tfrac {8}{5}}\right)\left({\tfrac {3}{5}}\right)=\left({\tfrac {2}{5}}\right)\left({\tfrac {3}{5}}\right)-\left({\tfrac {3}{5}}\right)=-\left({\tfrac {2}{3}}\right)=1$

$\left({\tfrac {-24}{7}}\right)=\left({\tfrac {-1}{7}}\right)\left({\tfrac {24}{7}}\right)=-\left({\tfrac {24}{7}}\right)=-\left({\tfrac {8}{7}}\right)\left({\tfrac {3}{7}}\right)=-\left({\tfrac {2}{7}}\right)\left({\tfrac {3}{7}}\right)=-\left({\tfrac {3}{7}}\right)=\left({\tfrac {4}{3}}\right)=1$

Analysis

Calculating the Jacobi symbol is similar to computing the gcd using the Euclidean algorithm.

$\operatorname {Euclid} (a,b)$

$\operatorname {if} \;(a\leq 0\;\operatorname {or} \;b\leq 0)\operatorname {fail}$

$\operatorname {if} \;(a=b)\operatorname {return} a$

$\operatorname {return} \operatorname {Euclid} (b{\bmod {a}},a)$

$\operatorname {end} \operatorname {Euclid}$

$\operatorname {Jacobi} (a,m)$

$\operatorname {if} \;(m<0\;\operatorname {or} \;m\equiv 0{\pmod {2}})$ $\operatorname {fail}$

$\operatorname {if} \;(a=0)$ $\operatorname {return} 0$

$\operatorname {if} \;(a=1)$ $\operatorname {return} 1$

Examine the bits in $a$ to find $a=s2^{k}a'$ where

$s=\pm 1,\;k\geq 0,\;a'>0,\;a'\equiv 1{\pmod {2}}.$

$\operatorname {if} \;(s<0\operatorname {and} m\equiv 3{\pmod {4}})$

$\operatorname {return} -\operatorname {Jacobi} (2^{k}a',m)$

$\operatorname {if} \;(k\equiv 1{\pmod {2}}\operatorname {and} m\equiv \pm 3{\pmod {8}})$

$\operatorname {return} -\operatorname {Jacobi} (a',m)$

$\operatorname {if} \;(a'\equiv 3{\pmod {4}}\operatorname {and} m\equiv 3{\pmod {4}})$

$\operatorname {return} -\operatorname {Jacobi} (m{\bmod {a}}',a')$

$\operatorname {return} \operatorname {Jacobi} (m{\bmod {a}}',a')$

$\operatorname {end} \operatorname {Jacobi}$

To show the parallel use the notation $[{\tfrac {a}{b}}]$for the gcd

$[{\tfrac {13}{21}}]=[{\tfrac {8}{13}}]=[{\tfrac {5}{8}}]=[{\tfrac {3}{5}}]=[{\tfrac {2}{3}}]=[{\tfrac {1}{2}}]=1$

Lamé’s Theorem (1844) states that the number of $\operatorname {mod}$ evaluations to compute a gcd is at most five times the number of base-ten digits of the smaller number. The Jacobi calculation does the same sort of recursion but sometimes divides by powers of 4. This has the effect of skipping ahead (the example would stop after the first step), reducing the number of $\operatorname {mod}$ operations and also reducing the size of the numbers compared to Euclid. In other words, the Lamé bound applies to Jacobi as well.

So, for example 2000-digit numbers will require about twice as many $\operatorname {mod}$s as 1000-digit ones. The cost of $\operatorname {mod}$ may go up with the number of digits.

Machine calculation

The algorithm is well-suited to machine calculations since its running time is $O(\min(\log a,\log m))$ and it requires negligeable storage. A number of authors have published code to evaluate Jacobi. The Lua and C++ routines below replace the recursion with a loop.

Lua code

function jacobi(a, m)
  assert(m > 0 and m % 2 == 1, "m must be positive and odd")

  local t = 1                      -- returned value

  while true do

    if a == 1 then 
       return t                             -- success t is the Jacobi symbol
    elseif a == 0 then 
       return 0                              -- a and m were not relatively prime
    end

    if a < 0 then
       a = -a                            -- if a is negative set a = |a|
       if m % 4 == 3 then                -- and evaluate (-1|m)
         t = -t
       end
    end
                                           -- a is positive
    local p = 0                       -- power of 2 dividing a
    while a % 2 == 0 do
      p = p + 1
      a = a / 2
    end
    if p % 2 == 1 then                   -- if the power of 2 is odd
      if m % 8 == 3 or m % 8 == 5 then     -- evaluate (2|m)
        t = -t
      end
    end
                                         -- a is odd
    if m % 4 == 3 and a % 4 == 3 then    -- does inverting the symbol
      t = -t                             -- change its sign?
    end 

    local temp = a                       -- next iteration is (m mod a|a)
    a = m % a
    m = temp
end

C++ code

int jacobi(int a, int m) {
    assert(m > 0 && m % 2 == 1);
    
    int t = 1;      // return value (accumulated sign)
    
    while (1) {

        if (a == 1) return t;        // success 
        if (a == 0) return 0;        // a and m were not coprime

        if (a < 0) {               // if a is negative replace it with the absolute value 
           a = -a;                 // and evaluate (-1|m)
           if (m % 4 == 3) t = -t;     
        }                          // a is positive

        int p = 0;                 // power of 2 dividing a        
        while (a % 2 == 0) {
            a /= 2;
            p++;
        }                          // a is odd
        if (p % 2 == 1)                                  // if the power of 2 was odd
            if (m % 8 == 3 || m % 8 == 5)   t = -t;      // evaluate (2|m)
                                                      
        if (m % 4 == 3 && a % 4 == 3) t = -t;              // evaluate (m|a)

        int temp = a;                                    // next iteration is m mod a over a
        a = m % a;
        m = temp;
    }
}

Uses

The Jacobi symbol is of theoretical interest in number theory, but its main use is computational. Cryptography in particular uses large prime numbers. A number of primality testing and integer factorization algorithms take advantage of the fact that Jacobi symbols can be computed quickly.

Because Euler's criterion is not valid for composite $m$, the Jacobi symbol can be used to detect composite numbers. Pick a random number $a$ and calculate the Jacobi symbol $\left({\tfrac {a}{m}}\right)$. If $\left({\tfrac {a}{m}}\right)\not \equiv a^{\tfrac {m-1}{2}}{\pmod {m}}$ then $m$ is composite; this is the basis of the Solovay–Strassen primality test. In some algorithms, such as the Lucas–Lehmer primality test, the value of certain Jacobi symbols is known theoretically and can be used to detect (hardware or software) errors.

An example of a factoring algorithm that uses Jacobi symbols is the continued fraction algorithm To factor $N$it tries to find numbers satisfying $x^{2}\equiv y^{2}{\pmod {N}}$. This involves constructing a database of primes and quadratic residues which requires multiple Jacobi symbol evaluations.

History

The Legendre symbol was introduced in 1798. It is not practical for calculations because it requires factorization into primes before it can be inverted. Jacobi introduced his symbol in 1837. to facilitate calculation. As explained here Gauss' first proof of quadratic reciprocity considers composite moduli and obtains some special cases of the Jacobi symbol.

Table

(⁠k/n⁠)   for  1≤ k ≤ 30,   1≤ n ≤ 59,   n odd.

k n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
1	−1	1	1	−1	1	1	1	1	−1	1	1	1	1	1	1	−1	1	1	1	1	1	1	1	1	−1	1	1	1	1	1
3	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
5	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0
7	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1
9	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0
11	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1
13	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1
15	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0
17	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1	−1	1	1	0	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1
19	1	−1	−1	1	1	1	1	−1	1	−1	1	−1	−1	−1	−1	1	1	−1	0	1	−1	−1	1	1	1	1	−1	1	−1	1
21	1	−1	0	1	1	0	0	−1	0	−1	−1	0	−1	0	0	1	1	0	−1	1	0	1	−1	0	1	1	0	0	−1	0
23	1	1	1	1	−1	1	−1	1	1	−1	−1	1	1	−1	−1	1	−1	1	−1	−1	−1	−1	0	1	1	1	1	−1	1	−1
25	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0
27	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
29	1	−1	−1	1	1	1	1	−1	1	−1	−1	−1	1	−1	−1	1	−1	−1	−1	1	−1	1	1	1	1	−1	−1	1	0	1
31	1	1	−1	1	1	−1	1	1	1	1	−1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	1	−1	−1	1	−1	−1
33	1	1	0	1	−1	0	−1	1	0	−1	0	0	−1	−1	0	1	1	0	−1	−1	0	0	−1	0	1	−1	0	−1	1	0
35	1	−1	1	1	0	−1	0	−1	1	0	1	1	1	0	0	1	1	−1	−1	0	0	−1	−1	−1	0	−1	1	0	1	0
37	1	−1	1	1	−1	−1	1	−1	1	1	1	1	−1	−1	−1	1	−1	−1	−1	−1	1	−1	−1	−1	1	1	1	1	−1	1
39	1	1	0	1	1	0	−1	1	0	1	1	0	0	−1	0	1	−1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0
41	1	1	−1	1	1	−1	−1	1	1	1	−1	−1	−1	−1	−1	1	−1	1	−1	1	1	−1	1	−1	1	−1	−1	−1	−1	−1
43	1	−1	−1	1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	1	−1	−1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1
45	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0
47	1	1	1	1	−1	1	1	1	1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	1	−1	−1	1	1	−1	1	1	−1	−1
49	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1
51	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	1	0	1	0	0	1	1	0	−1	1	0	1	−1	0	−1	1	0
53	1	−1	−1	1	−1	1	1	−1	1	1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1	−1	1	1	−1	−1	1	1	−1
55	1	1	−1	1	0	−1	1	1	1	0	0	−1	1	1	0	1	1	1	−1	0	−1	0	−1	−1	0	1	−1	1	−1	0
57	1	1	0	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	−1	0	0	−1	0	−1	−1	0	1	−1	0	1	1	0
59	1	−1	1	1	1	−1	1	−1	1	−1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	−1	−1	1	1	1	1	1	−1

See also

• Kronecker symbol, a generalization of the Jacobi symbol to all integers.
• Power residue symbol, a generalization of the Jacobi symbol to higher powers residues.

References

Books

• Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Berlin: Springer. ISBN 3-540-55640-0.

• Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0198531715

• Ireland, Kenneth; Rosen, Michael (1990). A Classical Introduction to Modern Number Theory (Second ed.). New York: Springer. ISBN 0-387-97329-X.
• Lemmermeyer, Franz (2000). Reciprocity Laws: from Euler to Eisenstein. Berlin: Springer. ISBN 3-540-66957-4.
• Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5

Journal articles

• Shallit, Jeffrey (December 1990). "On the Worst Case of Three Algorithms for Computing the Jacobi Symbol". Journal of Symbolic Computation. 10 (6): 593–61. doi:10.1016/S0747-7171(08)80160-5. Computer science technical report PCS-TR89-140.
• Vallée, Brigitte; Lemée, Charly (October 1998). Average-case analyses of three algorithms for computing the Jacobi symbol (Technical report). CiteSeerX 10.1.1.32.3425.
• Eikenberry, Shawna Meyer; Sorenson, Jonathan P. (October 1998). "Efficient Algorithms for Computing the Jacobi Symbol" (PDF). Journal of Symbolic Computation. 26 (4): 509–523. CiteSeerX 10.1.1.44.2423. doi:10.1006/jsco.1998.0226.