LegendreSymbol

The Legendre symbol (n/p): whether n is a quadratic residue mod the odd prime p.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaLegendre symbol↗MathWorldLegendreSymbol↗WikidataQ748339↗Wolfram LanguageJacobiSymbol!↗

LegendreSymbol(n, p)the Legendre symbol $\left(\frac{n}{p}\right)$.

SageMathlegendre_symbol(n, p)SymPylegendre_symbol(n, p)

Typed signatures

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

Domain: Number theory

Details

• 1 if $n$ is a nonzero quadratic residue mod $p$, $-1$ if it is a nonresidue, 0 if $p\mid n$.
• Defined only for an odd prime $p$; compute-engine leaves the call symbolic for any other $p$.
• The prime case of JacobiSymbol and KroneckerSymbol — all three agree wherever the domains overlap.

Plot

Examples

Basic #

2 is a quadratic residue mod 7: 3² ≡ 2 (mod 7)

live ↗

In$\mathrm{LegendreSymbol}(2, 7)$Out$1$

3 is not a quadratic residue mod 7

live ↗

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

0 when p divides n

live ↗

In$\mathrm{LegendreSymbol}(14, 7)$Out$0$

Scope #

Listable in $n$: the residues mod 7 are 1, 2, 4

live ↗

In$\mathrm{LegendreSymbol}(\bigl\lbrack1, 2, 3, 4, 5, 6\bigr\rbrack, 7)$Out$\bigl\lbrack1, 1, -1, 1, -1, -1\bigr\rbrack$

Properties #

$-1$ is a residue mod $p$ exactly when $p\equiv1\pmod4$

live ↗

In$\mathrm{LegendreSymbol}(-1, 13)$Out$1$

Euler's criterion: $(a/p)\equiv a^{(p-1)/2}\pmod p$, here $3^3\equiv6\equiv-1$. See PowerMod

live ↗

In$\mathrm{LegendreSymbol}(3, 7)=\mathrm{PowerMod}(3, 3, 7)-7$Out$\mathrm{True}$

Possible issues #

9 is not prime, so the call stays symbolic; see JacobiSymbol

live ↗

In$\mathrm{LegendreSymbol}(2, 9)$Out$\mathrm{LegendreSymbol}(2, 9)$

About

Examples	7
Checked against	Wolfram Language 6 agree1 differSageMath 6 agree1 errorSymPy 6 agree1 errormathlib4 4 agree1 unevaluated1 error
Crosswalk	WikipediaMathWorldWikidataWolfram LanguageSageMathSymPy

Implementation

mappedsympypackages/oracle/src/mappings.ts

SymPy's legendre_symbol raises unless the lower argument is an odd prime.

mappedsagepackages/oracle/src/mappings.ts

mappedmathlib4packages/oracle/src/mappings.ts

Mathlib's legendreSym needs a Fact p.Prime instance a literal cannot supply, so this reads jacobiSym a p, which Mathlib proves equal to legendreSym p a at an odd prime p (jacobiSym.legendreSym.to_jacobiSym); a composite or even p is outside the Legendre domain and gives the Jacobi value or zero.

See also: JacobiSymbol, KroneckerSymbol