# Jacobi (problemes formula)

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

where is the prime factorization of .

The Legendre symbol is defined for all integers and all odd primes 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)

Given two integers and , returns the Jacobi symbol .

$$\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.$$