# Jacobi

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 $\left(\frac{a}{n}\right)$ is defined as the product of the Legendre symbols corresponding to the prime factors of $n$:

$\left(\frac{a}{n}\right)={\left(\frac{a}{{p}_{1}}\right)}^{{\alpha }_{1}}{\left(\frac{a}{{p}_{2}}\right)}^{{\alpha }_{2}}\cdots {\left(\frac{a}{{p}_{k}}\right)}^{{\alpha }_{k}}$

where $n={p}_{1}^{{\alpha }_{1}}{p}_{2}^{{\alpha }_{2}}\cdots {p}_{k}^{{\alpha }_{k}}$ is the prime factorization of $n$.

The Legendre symbol $\left(\frac{a}{p}\right)$ is defined for all integers $a$ and all odd primes $p$ by

$\left(\frac{a}{p}\right)=\left\{\begin{array}{l}\begin{array}{l}-1\mathrm{if}a\not\equiv 0\left(\mathrm{mod}p\right)\mathrm{and}\mathrm{there}\mathrm{is}\mathrm{no}\mathrm{integer}x:a\equiv {x}^{2}\mathit{}\left(\mathrm{mod}p\right),\\ 0\mathrm{if}a\equiv 0\left(\mathrm{mod}p\right),\end{array}\\ 1\mathrm{if}a\not\equiv 0\left(\mathrm{mod}p\right)\mathrm{and}\mathrm{for}\mathrm{some}\mathrm{integer}x:a\equiv {x}^{2}\left(\mathrm{mod}p\right).\end{array}\right\$

## Syntax

```jacobi(Integer, Integer)
```

## Description

Given two integers $a$ and $n$, returns the Jacobi symbol $\left(\frac{a}{p}\right)$.