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)

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