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{array}{cc}1& \text{hvis }\mathrm{\exists }n\in \mathbb{Z}:a\equiv n^2(\mathrm{mod}p)\text{ og }a\equiv ̸0(\mathrm{mod}p),\\ 0& \text{hvis }a\equiv 0(\mathrm{mod}p),\\ -1& \text{ellers}.\end{array}$

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