JacobiSymbol

The Jacobi symbol (n/m), generalising the Legendre symbol to composite m.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaJacobi symbol↗MathWorldJacobiSymbol↗WikidataQ241015↗Wolfram LanguageJacobiSymbol✓↗Rosetta CodeJacobi symbol↗

JacobiSymbol(n, m)the Jacobi symbol $\left(\frac{n}{m}\right)$.

SageMathjacobi_symbol(n, m)SymPyjacobi_symbol(n, m)Juliajacobi_symbol(ZZ(n), ZZ(m))

Typed signatures

Type	Package	Applies
(integer, integer) -> integer	compute-engine	always

Domain: Number theory

Details

• Generalizes the Legendre symbol from prime $m$ to any odd $m$, by multiplying the Legendre symbols of $m$'s prime factors.
• 0 whenever $n$ and $m$ share a factor.
• Completely multiplicative in the top argument: $\left(\frac{a}{m}\right)\left(\frac{b}{m}\right)=\left(\frac{ab}{m}\right)$.
• By convention $\left(\frac{n}{1}\right)=1$ for every $n$.
• Unlike the Legendre symbol, $\left(\frac{n}{m}\right)=1$ doesn't imply $n$ is a quadratic residue mod $m$ when $m$ is composite.

Plot

Examples

Basic #

0 whenever n and m share a factor

live ↗

In$\mathrm{JacobiSymbol}(10, 5)$Out$0$

3 is not a quadratic residue mod 5 (the residues are 1 and 4)

live ↗

In$\mathrm{JacobiSymbol}(3, 5)$Out$-1$

live ↗

In$\mathrm{JacobiSymbol}(1\,001, 9\,907)$Out$-1$

Scope #

Threads element-wise over a list, as Wolfram's Listable heads do

live ↗

In$\mathrm{JacobiSymbol}(\bigl\lbrack2, 3, 5, 7, 11\bigr\rbrack, 3)$Out$\bigl\lbrack-1, 0, -1, 1, -1\bigr\rbrack$

Larger arguments: $10^{10}+1$ against the 1000th prime, 7919

live ↗

In$\mathrm{JacobiSymbol}(10^{10}+1, \mathrm{NthPrime}(1\,000))$Out$1$

Threads over a list of odd moduli; $0$ where $\gcd(-3,n)>1$

live ↗

In$\mathrm{JacobiSymbol}(-3, \bigl\lbrack1, 3, 5, 7\bigr\rbrack)$Out$\bigl\lbrack1, 0, -1, 1\bigr\rbrack$

Properties #

Completely multiplicative in the top argument: $(a/m)(b/m)=(ab/m)$

live ↗

In$\mathrm{JacobiSymbol}(3, 7)\mathrm{JacobiSymbol}(5, 7)=\mathrm{JacobiSymbol}(3×5, 7)$Out$\mathrm{True}$

Quadratic reciprocity: $(p/q)(q/p)=(-1)^{\frac{p-1}2\frac{q-1}2}$, $-1$ as $3\equiv7\equiv3\pmod4$

live ↗

In$\mathrm{JacobiSymbol}(3, 7)\mathrm{JacobiSymbol}(7, 3)$Out$-1$

$(-1/m)=(-1)^{(m-1)/2}$

live ↗

In$\mathrm{JacobiSymbol}(-1, 7)$Out$-1$

$-5\equiv1 \pmod 3$ is a square, so the symbol is $1$

live ↗

In$\mathrm{JacobiSymbol}(-5, 3)$Out$1$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

$-4\equiv2 \pmod 3$ is a non-residue

live ↗

In$\mathrm{JacobiSymbol}(-4, 3)$Out$-1$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

A multiple of the modulus gives $0$

live ↗

In$\mathrm{JacobiSymbol}(-3, 3)$Out$0$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

$-2\equiv1$, a residue mod 3

live ↗

In$\mathrm{JacobiSymbol}(-2, 3)$Out$1$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

$-1$ is not a square mod 3, since $3\equiv3 \pmod 4$

live ↗

In$\mathrm{JacobiSymbol}(-1, 3)$Out$-1$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

Zero is never coprime to the modulus, so the symbol vanishes

live ↗

In$\mathrm{JacobiSymbol}(0, 3)$Out$0$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

One is always a residue

live ↗

In$\mathrm{JacobiSymbol}(1, 3)$Out$1$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

$2$ is a non-residue mod 3

live ↗

In$\mathrm{JacobiSymbol}(2, 3)$Out$-1$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

Shares a factor with the modulus: $0$

live ↗

In$\mathrm{JacobiSymbol}(3, 3)$Out$0$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

A perfect square gives $1$ when coprime

live ↗

In$\mathrm{JacobiSymbol}(4, 3)$Out$1$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

$5\equiv2$, a non-residue

live ↗

In$\mathrm{JacobiSymbol}(5, 3)$Out$-1$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

Another multiple of 3, another $0$

live ↗

In$\mathrm{JacobiSymbol}(6, 3)$Out$0$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

$7\equiv1 \pmod 3$, so $1$

live ↗

In$\mathrm{JacobiSymbol}(7, 3)$Out$1$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

$8\equiv2$, so $-1$

live ↗

In$\mathrm{JacobiSymbol}(8, 3)$Out$-1$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

Every third value in $a$ drops to $0$

live ↗

In$\mathrm{JacobiSymbol}(9, 3)$Out$0$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

The pattern $1,-1,0$ repeats with period 3 in $a$

live ↗

In$\mathrm{JacobiSymbol}(10, 3)$Out$1$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

$\gcd(-5,5)=5$, so the symbol is $0$

live ↗

In$\mathrm{JacobiSymbol}(-5, 5)$Out$0$

Known value · Wolfram MathematicalFunctionData, JacobiSymbol

Possible issues #

By convention the symbol is 1 whenever $m=1$

live ↗

In$\mathrm{JacobiSymbol}(0, 1)$Out$1$

$(2/15)=(2/3)(2/5)=1$, yet 2 is not a square mod 15

live ↗

In$\mathrm{JacobiSymbol}(2, 15)$Out$1$

About

Examples	28
Checked against	Wolfram Language 28 agreeSageMath 28 agreeSymPy 28 agreemathlib4 25 agree2 errorJulia 27 agree
Crosswalk	WikipediaMathWorldWikidataWolfram LanguageSageMathSymPyJuliaRosetta Code

Implementation

mappedsympypackages/oracle/src/mappings.ts

SymPy's jacobi_symbol raises unless the lower argument is odd and positive.

mappedsagepackages/oracle/src/mappings.ts

mappedjuliapackages/oracle/src/mappings.ts

mappedmathlib4packages/oracle/src/mappings.ts

Mathlib's jacobiSym a b is the product of Legendre symbols over the prime factors of b, for any natural b: at an even b the factor at 2 is the quadratic character of ZMod 2, not the Kronecker symbol, so only an odd positive b is comparable.

See also: PowerMod, LegendreSymbol, KroneckerSymbol