Legendresymbolen

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

${\displaystyle \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

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

Se även

• Jacobisymbolen
• Kvadratisk rest
• Kvadratiska reciprocitetssatsen