Legendresymbolet

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

$\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 $\left({\frac {a}{p}}\right)=1$ kaldes $a$ en kvadratisk rest modulo $p$.