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

$\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.

Viktiga egenskaper

• $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\mathrm{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\mathrm{mod}p\Rightarrow \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$
• $\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}=\{\begin{array}{cc}1,& omp\equiv 1\mathrm{mod}4\\ -1,& omp\equiv 3\mathrm{mod}4\end{array}$
• $\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}=\{\begin{array}{cc}1,& omp\equiv 1el.7\mathrm{mod}8\\ -1,& omp\equiv 3el.5\mathrm{mod}8\end{array}$

Se även

• Jacobisymbolen
• Kvadratisk rest
• Kvadratiska reciprocitetssatsen