Legendresymbolen

Legendresymbolen har fått sitt namn efter den franska matematikern Adrien-Marie Legendre och används framförallt inom talteorin, samt även kryptografi. 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

<math>\left(\frac{a}{p}\right)</math>

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.

Viktiga egenskaper

<math>\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \ \operatorname{mod} \ p</math> (Eulers kriterium)
<math>\left(\frac{a^2}{p}\right) = 1</math>
<math>\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \left(\frac{b}{p}\right)</math>
<math>a\equiv b\ \operatorname{mod}\ p \ \ \Rightarrow \ \ \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)</math>
<math>\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.</math>
<math>\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.</math>