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