Jacobi (problemes formula)

Returns the Jacobi symbol. The Jacobi symbol is a generalization of the Legendre symbol. For any integer $a$ and any positive odd integer $n$ , the Jacobi symbol $open parentheses a over n close parentheses$ is defined as the product of the Legendre symbols corresponding to the prime factors of $n$ :

$open parentheses a over n close parentheses equals open parentheses a over p subscript 1 close parentheses to the power of alpha subscript 1 end exponent open parentheses a over p subscript 2 close parentheses to the power of alpha subscript 2 end exponent midline horizontal ellipsis open parentheses a over p subscript k close parentheses to the power of alpha subscript k end exponent$

where $n equals p subscript 1 superscript alpha subscript 1 end superscript p subscript 2 superscript alpha subscript 2 end superscript midline horizontal ellipsis p subscript k superscript alpha subscript k end superscript$ is the prime factorization of $n$ .

The Legendre symbol $open parentheses a over p close parentheses$ is defined for all integers $a$ and all odd primes $p$ by

$$\left(\frac ap\right)=\left\{\begin{array}{c}0\;\text{if }\;a\equiv0\;(\text{mod }p)\\1\text{ if }a\;\not\equiv0\;(\text{mod }p)\;\text{and for some integer }x:\;a\;\equiv x^2\;(\text{mod }p)\\-1\;\text{if }a\not\equiv0\;(\text{mod }p)\;\text{and there is no such }x\end{array}\right.$$

jacobi(Integer, Integer)

Description

jacobi(Integer, Integer)

Given two integers $a$ and $n$ , returns the Jacobi symbol $open parentheses a over p close parentheses$ .

Legendre (problemes fórmula), Lucas

$$\left(\frac ap\right)=\left\{\begin{array}{c}0\;\text{if }\;a\equiv0\;(\text{mod }p)\\1\text{ if }a\;\not\equiv0\;(\text{mod }p)\;\text{and for some integer }x:\;a\;\equiv x^2\;(\text{mod }p)\\-1\;\text{if }a\not\equiv0\;(\text{mod }p)\;\text{and there is no such }x\end{array}\right.$$

Jacobi (problemes formula)

Syntax

Description

jacobi(Integer, Integer)

Related functions