Jacobi symbol · Lablypedia

Related on Lably

Through Modular arithmetic, Primality test and Integer factorization

Lab · Class 5–6Fractions Visualizer Lab · Class 6–11How India Is Governed Lab · Class 1–6Patterns Lab · Class 8Squares & Square Roots

Definition

For any integer a and any positive odd integer n, the Jacobi symbol (⁠a/n⁠) is defined as the product of the Legendre symbols corresponding to the prime factors of n:

(\frac{a}{n}) := {(\frac{a}{p_{1}})}^{α_{1}} {(\frac{a}{p_{2}})}^{α_{2}} \dots {(\frac{a}{p_{k}})}^{α_{k}},

where

n = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{k}^{α_{k}}

is the prime factorization of n.

The Legendre symbol (⁠a/p⁠) is defined for all integers a and all odd primes p by

(\frac{a}{p}) := {\begin{aligned} 0 & if a \equiv 0 (\mod p), \\ 1 & if a ≢ 0 (\mod p) and for some integer x : a \equiv x^{2} (\mod p), \\ - 1 & if a ≢ 0 (\mod p) and there is no such x . \end{aligned}

Following the normal convention for the empty product, (⁠a/1⁠) = 1.

When the lower argument is an odd prime, the Jacobi symbol is equal to the Legendre symbol.

4 more chapters are free with a Lably account.

Table of values

The following is a table of values of Jacobi symbol (⁠a/n⁠) with n ≤ 59, a ≤ 30, n odd.

Properties

The following facts, even the reciprocity laws, are straightforward deductions from the definition of the Jacobi symbol and the corresponding properties of the Legendre symbol.

The Jacobi symbol is defined only when the upper argument ("numerator") is an integer and the lower argument ("denominator") is a positive odd integer.

1. If n is (an odd) prime, then the Jacobi symbol (⁠a/n⁠) is equal to (and written the same as) the corresponding Legendre symbol.

2. If a ≡ b (mod n), then

(\frac{a}{n}) = (\frac{b}{n}) = (\frac{a \pm k \cdot n}{n}) .

(\frac{a}{n}) = {\begin{cases} 0 & if gcd (a, n) \neq 1, \\ \pm 1 & if gcd (a, n) = 1. \end{cases}

If either the top or bottom argument is fixed, the Jacobi symbol is a completely multiplicative function in the remaining argument:

(\frac{a b}{n}) = (\frac{a}{n}) (\frac{b}{n}), so (\frac{a^{2}}{n}) = (\frac{a}{n})^{2} = + 1 or 0.

(\frac{a}{m n}) = (\frac{a}{m}) (\frac{a}{n}), so (\frac{a}{n^{2}}) = (\frac{a}{n})^{2} = + 1 or 0.

The law of quadratic reciprocity: if m and n are odd positive coprime integers, then

(\frac{m}{n}) (\frac{n}{m}) = (- 1)^{\frac{m - 1}{2} \cdot \frac{n - 1}{2}} = {\begin{cases} + 1 & if n \equiv 1 or m \equiv 1 (\mod 4), \\ - 1 & if n \equiv m \equiv 3 (\mod 4) . \end{cases}

and its supplements

(\frac{1}{n}) = (\frac{n}{1}) = + 1.

(\frac{- 1}{n}) = (- 1)^{\frac{n - 1}{2}} = {\begin{cases} + 1 & if n \equiv 1 (\mod 4), \\ - 1 & if n \equiv 3 (\mod 4) . \end{cases}

(\frac{2}{n}) = (- 1)^{\frac{n^{2} - 1}{8}} = {\begin{cases} + 1 & if n \equiv 1, 7 (\mod 8), \\ - 1 & if n \equiv 3, 5 (\mod 8) . \end{cases}

Combining properties 4 and 9 gives:

10.

(\frac{2 a}{n}) = (\frac{2}{n}) (\frac{a}{n}) = {\begin{cases} (\frac{a}{n}) & if n \equiv 1, 7 (\mod 8), \\ - (\frac{a}{n}) & if n \equiv 3, 5 (\mod 8) . \end{cases}

Combining properties 2, 6 and 10 gives:

11. If n ≡ m (mod 4a), then

(\frac{a}{n}) = (\frac{a}{m}) = (\frac{a}{n + 4 k | a |}) .

12.

(\frac{a}{n + 2 | a |}) = (\frac{a}{n}) (- 1)^{\frac{a (a - 1)}{2}} = {\begin{cases} (\frac{a}{n}) & if a \equiv 0, 1 (\mod 4), \\ - (\frac{a}{n}) & if a \equiv 2, 3 (\mod 4) . \end{cases}

Like the Legendre symbol:

If (⁠a/n⁠) = −1 then a is a quadratic nonresidue modulo n.
If a is a quadratic residue modulo n and gcd(a,n) = 1, then (⁠a/n⁠) = +1.

But, unlike the Legendre symbol:

If (⁠a/n⁠) = +1 then a may or may not be a quadratic residue modulo n.
If a is a quadratic nonresidue modulo n, then (⁠a/n⁠) may be −1 or +1.

This is because for a to be a quadratic residue modulo n, it has to be a quadratic residue modulo every prime factor of n. However, the Jacobi symbol equals +1 if, for example, a is a non-residue modulo exactly two of the prime factors of n.

Although the Jacobi symbol cannot be uniformly interpreted in terms of squares and non-squares, it can be uniformly interpreted as the sign of a permutation by Zolotarev's lemma.

The Jacobi symbol (⁠a/n⁠) is a Dirichlet character to the modulus n.

Calculating the Jacobi symbol

The above formulas lead to an efficient O(log a log b) algorithm for calculating the Jacobi symbol, analogous to the Euclidean algorithm for finding the gcd of two numbers. (This should not be surprising in light of rule 2.)

Reduce the "numerator" modulo the "denominator" using rule 2.
Extract any even "numerator" using rule 10.
If the "numerator" is 1, rules 3 and 4 give a result of 1. If the "numerator" and "denominator" are not coprime, rule 3 gives a result of 0.
Otherwise, the "numerator" and "denominator" are now odd positive coprime integers, so we can flip the symbol using rule 6, then return to step 1.

In addition to the codes below, Riesel has it in Pascal. The below implementations can be straightforwardly translated to any language with integer operations.

Implementation in Lua

<span id="mwBZc"></span><span class="kr" id="mwBZg">function</span><span class="w" id="mwBZk"> </span><span class="nf" id="mwBZo">jacobi</span><span class="p" id="mwBZs">(</span><span class="nv" id="mwBZw">a</span><span class="p" id="mwBZ0">,</span><span class="w" id="mwBZ4"> </span><span class="nv" id="mwBZ8">n</span><span class="p" id="mwBaA">)</span> <span class="w" id="mwBaE"> </span><span class="nb" id="mwBaI">assert</span><span class="p" id="mwBaM">(</span><span class="nv" id="mwBaQ">n</span><span class="w" id="mwBaU"> </span><span class="o" id="mwBaY">></span><span class="w" id="mwBac"> </span><span class="mi" id="mwBag">0</span><span class="w" id="mwBak"> </span><span class="ow" id="mwBao">and</span><span class="w" id="mwBas"> </span><span class="nv" id="mwBaw">n</span><span class="w" id="mwBa0"> </span><span class="o" id="mwBa4">%</span><span class="w" id="mwBa8"> </span><span class="mi" id="mwBbA">2</span><span class="w" id="mwBbE"> </span><span class="o" id="mwBbI">==</span><span class="w" id="mwBbM"> </span><span class="mi" id="mwBbQ">1</span><span class="p" id="mwBbU">)</span> <span class="w" id="mwBbY"> </span><span class="nv" id="mwBbc">a</span><span class="w" id="mwBbg"> </span><span class="o" id="mwBbk">=</span><span class="w" id="mwBbo"> </span><span class="nv" id="mwBbs">a</span><span class="w" id="mwBbw"> </span><span class="o" id="mwBb0">%</span><span class="w" id="mwBb4"> </span><span class="nv" id="mwBb8">n</span><span class="w" id="mwBcA"> </span><span class="c1" id="mwBcE">-- step 1</span> <span class="w" id="mwBcI"> </span><span class="nv" id="mwBcM">t</span><span class="w" id="mwBcQ"> </span><span class="o" id="mwBcU">=</span><span class="w" id="mwBcY"> </span><span class="mi" id="mwBcc">1</span><span class="w" id="mwBcg"> </span><span class="c1" id="mwBck">-- sign of return value</span> <span class="w" id="mwBco"> </span><span class="kr" id="mwBcs">while</span><span class="w" id="mwBcw"> </span><span class="nv" id="mwBc0">a</span><span class="w" id="mwBc4"> </span><span class="o" id="mwBc8">~=</span><span class="w" id="mwBdA"> </span><span class="mi" id="mwBdE">0</span><span class="w" id="mwBdI"> </span><span class="kr" id="mwBdM">do</span> <span class="w" id="mwBdQ"> </span><span class="kr" id="mwBdU">while</span><span class="w" id="mwBdY"> </span><span class="nv" id="mwBdc">a</span><span class="w" id="mwBdg"> </span><span class="o" id="mwBdk">%</span><span class="w" id="mwBdo"> </span><span class="mi" id="mwBds">2</span><span class="w" id="mwBdw"> </span><span class="o" id="mwBd0">==</span><span class="w" id="mwBd4"> </span><span class="mi" id="mwBd8">0</span><span class="w" id="mwBeA"> </span><span class="kr" id="mwBeE">do</span><span class="w" id="mwBeI"> </span><span class="c1" id="mwBeM">-- step 2, rule 10</span> <span class="w" id="mwBeQ"> </span><span class="nv" id="mwBeU">a</span><span class="w" id="mwBeY"> </span><span class="o" id="mwBec">=</span><span class="w" id="mwBeg"> </span><span class="nv" id="mwBek">a</span><span class="w" id="mwBeo"> </span><span class="o" id="mwBes">/</span><span class="w" id="mwBew"> </span><span class="mi" id="mwBe0">2</span> <span class="w" id="mwBe4"> </span><span class="nv" id="mwBe8">r</span><span class="w" id="mwBfA"> </span><span class="o" id="mwBfE">=</span><span class="w" id="mwBfI"> </span><span class="nv" id="mwBfM">n</span><span class="w" id="mwBfQ"> </span><span class="o" id="mwBfU">%</span><span class="w" id="mwBfY"> </span><span class="mi" id="mwBfc">8</span> <span class="w" id="mwBfg"> </span><span class="kr" id="mwBfk">if</span><span class="w" id="mwBfo"> </span><span class="nv" id="mwBfs">r</span><span class="w" id="mwBfw"> </span><span class="o" id="mwBf0">==</span><span class="w" id="mwBf4"> </span><span class="mi" id="mwBf8">3</span><span class="w" id="mwBgA"> </span><span class="ow" id="mwBgE">or</span><span class="w" id="mwBgI"> </span><span class="nv" id="mwBgM">r</span><span class="w" id="mwBgQ"> </span><span class="o" id="mwBgU">==</span><span class="w" id="mwBgY"> </span><span class="mi" id="mwBgc">5</span><span class="w" id="mwBgg"> </span><span class="kr" id="mwBgk">then</span> <span class="w" id="mwBgo"> </span><span class="nv" id="mwBgs">t</span><span class="w" id="mwBgw"> </span><span class="o" id="mwBg0">=</span><span class="w" id="mwBg4"> </span><span class="o" id="mwBg8">-</span><span class="nv" id="mwBhA">t</span> <span class="w" id="mwBhE"> </span><span class="kr" id="mwBhI">end</span> <span class="w" id="mwBhM"> </span><span class="kr" id="mwBhQ">end</span> <span class="w" id="mwBhU"> </span><span class="kr" id="mwBhY">if</span><span class="w" id="mwBhc"> </span><span class="nv" id="mwBhg">a</span><span class="w" id="mwBhk"> </span><span class="o" id="mwBho">%</span><span class="w" id="mwBhs"> </span><span class="mi" id="mwBhw">4</span><span class="w" id="mwBh0"> </span><span class="o" id="mwBh4">==</span><span class="w" id="mwBh8"> </span><span class="mi" id="mwBiA">3</span><span class="w" id="mwBiE"> </span><span class="ow" id="mwBiI">and</span><span class="w" id="mwBiM"> </span><span class="nv" id="mwBiQ">n</span><span class="w" id="mwBiU"> </span><span class="o" id="mwBiY">%</span><span class="w" id="mwBic"> </span><span class="mi" id="mwBig">4</span><span class="w" id="mwBik"> </span><span class="o" id="mwBio">==</span><span class="w" id="mwBis"> </span><span class="mi" id="mwBiw">3</span><span class="w" id="mwBi0"> </span><span class="kr" id="mwBi4">then</span><span class="w" id="mwBi8"> </span><span class="c1" id="mwBjA">-- step 4, rule 6: flip sign</span> <span class="w" id="mwBjE"> </span><span class="nv" id="mwBjI">t</span><span class="w" id="mwBjM"> </span><span class="o" id="mwBjQ">=</span><span class="w" id="mwBjU"> </span><span class="o" id="mwBjY">-</span><span class="nv" id="mwBjc">t</span> <span class="w" id="mwBjg"> </span><span class="kr" id="mwBjk">end</span> <span class="w" id="mwBjo"> </span><span class="nv" id="mwBjs">a</span><span class="p" id="mwBjw">,</span><span class="w" id="mwBj0"> </span><span class="nv" id="mwBj4">n</span><span class="w" id="mwBj8"> </span><span class="o" id="mwBkA">=</span><span class="w" id="mwBkE"> </span><span class="nv" id="mwBkI">n</span><span class="p" id="mwBkM">,</span><span class="w" id="mwBkQ"> </span><span class="nv" id="mwBkU">a</span><span class="w" id="mwBkY"> </span><span class="c1" id="mwBkc">-- ... swap. Rearranging step 6 as (a/n) = k * (n/a), where k is +1 or -1.</span> <span class="w" id="mwBkg"> </span><span class="nv" id="mwBkk">a</span><span class="w" id="mwBko"> </span><span class="o" id="mwBks">=</span><span class="w" id="mwBkw"> </span><span class="nv" id="mwBk0">a</span><span class="w" id="mwBk4"> </span><span class="o" id="mwBk8">%</span><span class="w" id="mwBlA"> </span><span class="nv" id="mwBlE">n</span><span class="w" id="mwBlI"> </span><span class="c1" id="mwBlM">-- and step 1 again</span> <span class="w" id="mwBlQ"> </span><span class="kr" id="mwBlU">end</span> <span class="w" id="mwBlY"> </span><span class="kr" id="mwBlc">if</span><span class="w" id="mwBlg"> </span><span class="nv" id="mwBlk">n</span><span class="w" id="mwBlo"> </span><span class="o" id="mwBls">==</span><span class="w" id="mwBlw"> </span><span class="mi" id="mwBl0">1</span><span class="w" id="mwBl4"> </span><span class="kr" id="mwBl8">then</span><span class="w" id="mwBmA"> </span><span class="c1" id="mwBmE">-- step 3. at this point, n = gcd(a, n) (as initially passed)</span> <span class="w" id="mwBmI"> </span><span class="kr" id="mwBmM">return</span><span class="w" id="mwBmQ"> </span><span class="nv" id="mwBmU">t</span> <span class="w" id="mwBmY"> </span><span class="kr" id="mwBmc">else</span> <span class="w" id="mwBmg"> </span><span class="kr" id="mwBmk">return</span><span class="w" id="mwBmo"> </span><span class="mi" id="mwBms">0</span> <span class="w" id="mwBmw"> </span><span class="kr" id="mwBm0">end</span> <span class="kr" id="mwBm4">end</span>

(Lua uses a 64-bit signed integer type.)

Implementation in C/C++

<span id="mwBnU"></span><span class="c1" id="mwBnY">// a/n is represented as (a,n)</span> <span class="kt" id="mwBnc">int</span><span class="w" id="mwBng"> </span><span class="nf" id="mwBnk">jacobi</span><span class="p" id="mwBno">(</span><span class="kt" id="mwBns">int</span><span class="w" id="mwBnw"> </span><span class="n" id="mwBn0">a</span><span class="p" id="mwBn4">,</span><span class="w" id="mwBn8"> </span><span class="kt" id="mwBoA">int</span><span class="w" id="mwBoE"> </span><span class="n" id="mwBoI">n</span><span class="p" id="mwBoM">)</span><span class="w" id="mwBoQ"> </span><span class="p" id="mwBoU">{</span> <span class="w" id="mwBoY"> </span><span class="n" id="mwBoc">assert</span><span class="p" id="mwBog">(</span><span class="n" id="mwBok">n</span><span class="w" id="mwBoo"> </span><span class="o" id="mwBos">></span><span class="w" id="mwBow"> </span><span class="mi" id="mwBo0">0</span><span class="w" id="mwBo4"> </span><span class="o" id="mwBo8">&&</span><span class="w" id="mwBpA"> </span><span class="n" id="mwBpE">n</span><span class="w" id="mwBpI"> </span><span class="o" id="mwBpM">%</span><span class="w" id="mwBpQ"> </span><span class="mi" id="mwBpU">2</span><span class="w" id="mwBpY"> </span><span class="o" id="mwBpc">==</span><span class="w" id="mwBpg"> </span><span class="mi" id="mwBpk">1</span><span class="p" id="mwBpo">);</span> <span class="w" id="mwBps"> </span><span class="c1" id="mwBpw">// Step 1</span> <span class="w" id="mwBp0"> </span><span class="n" id="mwBp4">a</span><span class="w" id="mwBp8"> </span><span class="o" id="mwBqA">%=</span><span class="w" id="mwBqE"> </span><span class="n" id="mwBqI">n</span><span class="p" id="mwBqM">;</span> <span class="w" id="mwBqQ"> </span><span class="k" id="mwBqU">if</span><span class="w" id="mwBqY"> </span><span class="p" id="mwBqc">(</span><span class="n" id="mwBqg">a</span><span class="w" id="mwBqk"> </span><span class="o" id="mwBqo"><</span><span class="w" id="mwBqs"> </span><span class="mi" id="mwBqw">0</span><span class="p" id="mwBq0">)</span><span class="w" id="mwBq4"> </span><span class="n" id="mwBq8">a</span><span class="w" id="mwBrA"> </span><span class="o" id="mwBrE">+=</span><span class="w" id="mwBrI"> </span><span class="n" id="mwBrM">n</span><span class="p" id="mwBrQ">;</span><span class="w" id="mwBrU"> </span><span class="c1" id="mwBrY">// C returns negative (a%b) for negative a. Flip it to the mathematical modulo direction.</span> <span class="w" id="mwBrc"> </span><span class="kt" id="mwBrg">int</span><span class="w" id="mwBrk"> </span><span class="n" id="mwBro">t</span><span class="w" id="mwBrs"> </span><span class="o" id="mwBrw">=</span><span class="w" id="mwBr0"> </span><span class="mi" id="mwBr4">0</span><span class="p" id="mwBr8">;</span><span class="w" id="mwBsA"> </span><span class="c1" id="mwBsE">// sign of return value. XOR of bits 1 and 2 determines sign of return value</span> <span class="w" id="mwBsI"> </span><span class="k" id="mwBsM">while</span><span class="w" id="mwBsQ"> </span><span class="p" id="mwBsU">(</span><span class="n" id="mwBsY">a</span><span class="p" id="mwBsc">)</span><span class="w" id="mwBsg"> </span><span class="p" id="mwBsk">{</span> <span class="w" id="mwBso"> </span><span class="c1" id="mwBss">// Step 2</span> <span class="w" id="mwBsw"> </span><span class="k" id="mwBs0">while</span><span class="w" id="mwBs4"> </span><span class="p" id="mwBs8">(</span><span class="n" id="mwBtA">a</span><span class="w" id="mwBtE"> </span><span class="o" id="mwBtI">%</span><span class="w" id="mwBtM"> </span><span class="mi" id="mwBtQ">4</span><span class="w" id="mwBtU"> </span><span class="o" id="mwBtY">==</span><span class="w" id="mwBtc"> </span><span class="mi" id="mwBtg">0</span><span class="p" id="mwBtk">)</span><span class="w" id="mwBto"> </span><span class="n" id="mwBts">a</span><span class="w" id="mwBtw"> </span><span class="o" id="mwBt0">/=</span><span class="w" id="mwBt4"> </span><span class="mi" id="mwBt8">4</span><span class="p" id="mwBuA">;</span><span class="w" id="mwBuE"> </span><span class="c1" id="mwBuI">// shortcut</span> <span class="w" id="mwBuM"> </span><span class="k" id="mwBuQ">if</span><span class="w" id="mwBuU"> </span><span class="p" id="mwBuY">(</span><span class="n" id="mwBuc">a</span><span class="w" id="mwBug"> </span><span class="o" id="mwBuk">%</span><span class="w" id="mwBuo"> </span><span class="mi" id="mwBus">2</span><span class="w" id="mwBuw"> </span><span class="o" id="mwBu0">==</span><span class="w" id="mwBu4"> </span><span class="mi" id="mwBu8">0</span><span class="p" id="mwBvA">)</span><span class="w" id="mwBvE"> </span><span class="p" id="mwBvI">{</span> <span class="w" id="mwBvM"> </span><span class="n" id="mwBvQ">a</span><span class="w" id="mwBvU"> </span><span class="o" id="mwBvY">/=</span><span class="w" id="mwBvc"> </span><span class="mi" id="mwBvg">2</span><span class="p" id="mwBvk">;</span> <span class="w" id="mwBvo"> </span><span class="n" id="mwBvs">t</span><span class="w" id="mwBvw"> </span><span class="o" id="mwBv0">^=</span><span class="w" id="mwBv4"> </span><span class="n" id="mwBv8">n</span><span class="p" id="mwBwA">;</span><span class="w" id="mwBwE"> </span><span class="c1" id="mwBwI">// Could be "^= n & 6"; we only care about bits 1 and 2</span> <span class="w" id="mwBwM"> </span><span class="c1" id="mwBwQ">// This is an encoding of rule 10. Sign is flipped here if 2 <= n <= 5 (mod 8).</span> <span class="w" id="mwBwU"> </span><span class="c1" id="mwBwY">// Although n = 2,4 (mod 8) are also affected here, we know as a precondition n%2 == 1.</span> <span class="w" id="mwBwc"> </span><span class="p" id="mwBwg">}</span> <span class="w" id="mwBwk"> </span><span class="c1" id="mwBwo">// Step 4</span> <span class="w" id="mwBws"> </span><span class="n" id="mwBww">t</span><span class="w" id="mwBw0"> </span><span class="o" id="mwBw4">^=</span><span class="w" id="mwBw8"> </span><span class="n" id="mwBxA">a</span><span class="w" id="mwBxE"> </span><span class="o" id="mwBxI">&</span><span class="w" id="mwBxM"> </span><span class="n" id="mwBxQ">n</span><span class="w" id="mwBxU"> </span><span class="o" id="mwBxY">&</span><span class="w" id="mwBxc"> </span><span class="mi" id="mwBxg">2</span><span class="p" id="mwBxk">;</span><span class="w" id="mwBxo"> </span><span class="c1" id="mwBxs">// Flip sign by flipping bit 1 if a = n = 3 (mod 4). </span> <span class="w" id="mwBxw"> </span><span class="c1" id="mwBx0">// (Technically checks whether both a and n \in [3,4] (mod 4), but again, the precondition.)</span> <span class="w" id="mwBx4"> </span><span class="kt" id="mwBx8">int</span><span class="w" id="mwByA"> </span><span class="n" id="mwByE">r</span><span class="w" id="mwByI"> </span><span class="o" id="mwByM">=</span><span class="w" id="mwByQ"> </span><span class="n" id="mwByU">n</span><span class="w" id="mwByY"> </span><span class="o" id="mwByc">%</span><span class="w" id="mwByg"> </span><span class="n" id="mwByk">a</span><span class="p" id="mwByo">;</span><span class="w" id="mwBys"> </span><span class="c1" id="mwByw">// swap & step 1</span> <span class="w" id="mwBy0"> </span><span class="n" id="mwBy4">n</span><span class="w" id="mwBy8"> </span><span class="o" id="mwBzA">=</span><span class="w" id="mwBzE"> </span><span class="n" id="mwBzI">a</span><span class="p" id="mwBzM">;</span> <span class="w" id="mwBzQ"> </span><span class="n" id="mwBzU">a</span><span class="w" id="mwBzY"> </span><span class="o" id="mwBzc">=</span><span class="w" id="mwBzg"> </span><span class="n" id="mwBzk">r</span><span class="p" id="mwBzo">;</span> <span class="w" id="mwBzs"> </span><span class="p" id="mwBzw">}</span> <span class="w" id="mwBz0"> </span><span class="c1" id="mwBz4">// Step 3</span> <span class="w" id="mwBz8"> </span><span class="k" id="mwB0A">if</span><span class="w" id="mwB0E"> </span><span class="p" id="mwB0I">(</span><span class="n" id="mwB0M">n</span><span class="w" id="mwB0Q"> </span><span class="o" id="mwB0U">!=</span><span class="w" id="mwB0Y"> </span><span class="mi" id="mwB0c">1</span><span class="p" id="mwB0g">)</span> <span class="w" id="mwB0k"> </span><span class="k" id="mwB0o">return</span><span class="w" id="mwB0s"> </span><span class="mi" id="mwB0w">0</span><span class="p" id="mwB00">;</span> <span class="w" id="mwB04"> </span><span class="k" id="mwB08">else</span><span class="w" id="mwB1A"> </span><span class="k" id="mwB1E">if</span><span class="w" id="mwB1I"> </span><span class="p" id="mwB1M">((</span><span class="n" id="mwB1Q">t</span><span class="w" id="mwB1U"> </span><span class="o" id="mwB1Y">+</span><span class="w" id="mwB1c"> </span><span class="mi" id="mwB1g">2</span><span class="p" id="mwB1k">)</span><span class="w" id="mwB1o"> </span><span class="o" id="mwB1s">&</span><span class="w" id="mwB1w"> </span><span class="mi" id="mwB10">4</span><span class="p" id="mwB14">)</span> <span class="w" id="mwB18"> </span><span class="k" id="mwB2A">return</span><span class="w" id="mwB2E"> </span><span class="mi" id="mwB2I">-1</span><span class="p" id="mwB2M">;</span> <span class="w" id="mwB2Q"> </span><span class="k" id="mwB2U">else</span> <span class="w" id="mwB2Y"> </span><span class="k" id="mwB2c">return</span><span class="w" id="mwB2g"> </span><span class="mi" id="mwB2k">1</span><span class="p" id="mwB2o">;</span> <span class="p" id="mwB2s">}</span>

(The signed int type is only necessary on the return value; all other values may be instead unsigned integers.)

Primality testing

There is another way the Jacobi and Legendre symbols differ. If the Euler's criterion formula is used modulo a composite number, the result may or may not be the value of the Jacobi symbol, and in fact may not even be −1 or 1. For example,

\begin{matrix} (\frac{19}{45}) & = 1 & and & 19^{\frac{45 - 1}{2}} & \equiv 1 (\mod 45) . \\ (\frac{8}{21}) & = - 1 & but & 8^{\frac{21 - 1}{2}} & \equiv 1 (\mod 21) . \\ (\frac{5}{21}) & = 1 & but & 5^{\frac{21 - 1}{2}} & \equiv 16 (\mod 21) . \end{matrix}

So if it is unknown whether a number n is prime or composite, we can pick a random number a, calculate the Jacobi symbol (⁠a/n⁠) and compare it with Euler's formula; if they differ modulo n, then n is composite; if they have the same residue modulo n for many different values of a, then n is "probably prime".

This is the basis for the probabilistic Solovay–Strassen primality test and refinements such as the Baillie–PSW primality test and the Miller–Rabin primality test.

As an indirect use, it is possible to use it as an error detection routine during the execution of the Lucas–Lehmer primality test which, even on modern computer hardware, can take weeks to complete when processing Mersenne numbers over $\begin{matrix} 2^{136, 279, 841} - 1 \end{matrix}$ (the largest known Mersenne prime as of October 2024). In nominal cases, the Jacobi symbol:

$\begin{matrix} (\frac{s_{i} - 2}{M_{p}}) & = - 1 & i \neq 0 \end{matrix}$

This also holds for the final residue $\begin{matrix} s_{p - 2} \end{matrix}$ and hence can be used as a verification of probable validity. However, if an error occurs in the hardware, there is a 50% chance that the result will become 0 or 1 instead, and won't change with subsequent terms of $\begin{matrix} s \end{matrix}$ (unless another error occurs and changes it back to −1).

More in Number theory

On-Line Encyclopedia of Integer SequencesOnline database of integer sequences Recurrence relationPattern defining an infinite sequence of numbers Coprime integersTwo numbers without shared prime factors DivisorInteger that divides another integer P-adic numberNumber system extending the rational numbers Greatest common divisorLargest integer that divides given integers