# Legendre Symbol

The Legendre symbol is a function of $a$ and $p$ defined as :

$\left({\frac {a}{p}}\right)={\begin{cases}1&{\text{ if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{ if }}a{\text{ is a quadratic non-residue modulo }}p,\\0&{\text{ if }}a\equiv 0{\pmod {p}}.\end{cases}}$

Legendre symbol 的原始定義其實是這樣的 ( 兩個定義是等價的 ) :

$\left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}\quad {\text{ and }}\quad \left({\frac {a}{p}}\right)\in \{-1,0,1\}$

### Jacobi Symbol

The Jacobi symbol is a function of $a$ and $p$ defined as the product of Legendre symbols :

${\displaystyle \left({\frac {a}{p}}\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 ${\displaystyle p = p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}$

Jacobi symbol is a generalization of Legendre symbol