Legendresymbolen

Legendresymbolen har fått sitt namn efter den franska matematikern Adrien-Marie Legendre och används framförallt inom talteorin. Den används för att bestämma kvadratiska rester.

Om p är ett primtal och a är ett heltal relativt primt med p så definieras Legendresymbolen

$\left(\frac{a}{p}\right)$

att vara:

1 om a är en kvadratisk rest modulo p (det vill säga om det existerar ett heltal x så att x² ≡ a mod p)
-1 om a inte är en kvadratisk rest modulo p.
Definitionen utvidgas ibland till att Legendresymbolen är 0 om a är delbar med p.

[redigera] Viktiga egenskaper

$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \ \operatorname{mod} \ p$ (Eulers kriterium)
$\left(\frac{a^2}{p}\right) = 1$
$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \left(\frac{b}{p}\right)$
$a\equiv b\ \operatorname{mod}\ p \ \ \Rightarrow \ \ \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$
$\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = \left\{\begin{matrix} 1, & om\ p\equiv 1\ \operatorname{mod}\ 4\\ -1, & om\ p\equiv 3\ \operatorname{mod}\ 4 \end{matrix}\right.$
$\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = \left\{\begin{matrix} 1, & om\ p\equiv 1\ el.\ 7\ \operatorname{mod}\ 8\\ -1, & om\ p\equiv 3\ el.\ 5\ \operatorname{mod}\ 8 \end{matrix}\right.$