Skip to content

Legendre Symbol

有一個奇質數 p ,一個整數 a

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

有一個奇數 p ,一個整數 a

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