Legendresymbolet

Legendresymbolet ${\displaystyle \left({\frac {a}{p}}\right)}$ er en funktion fra talteorien, som fortæller om et heltal ${\displaystyle a}$ er en kvadratisk rest modulo et primtal ${\displaystyle p}$. Legendresymbolet er defineret på følgende vis:

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{hvis }}\exists n\in \mathbb {Z} :a\equiv n^{2}{\pmod {p}}{\text{ og }}a\not \equiv 0{\pmod {p}},\\0&{\text{hvis }}a\equiv 0{\pmod {p}},\\-1&{\text{ellers}}.\end{cases}}}$

Hvis ${\displaystyle \left({\frac {a}{p}}\right)=1}$ kaldes ${\displaystyle a}$ en kvadratisk rest modulo ${\displaystyle p}$.