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
![{\displaystyle \left({\frac {a}{p}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aad4dd123bb7bc0da377dec595d91761753ba294)
att vara:
- 1 om a är en kvadratisk rest modulo p (det vill säga om det existerar ett heltal x så att x2 ≡ 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
(Eulers kriterium) ![{\displaystyle \left({\frac {a^{2}}{p}}\right)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5b6f43df4f40202dbf365146ae39d7037387df5)
![{\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c8876ab646dd7c9976bc54dd7487527f77bd202)
![{\displaystyle a\equiv b\ \operatorname {mod} \ p\ \ \Rightarrow \ \ \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75f9a31d0a23de075fa58951c5ea1a5c5c1ac915)
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35e895b3ece7b8da96a8e3f79f69b3e868217271)
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6b90d37691606a1310497c5f93b6afe21083c27)
Se även
- Jacobisymbolen
- Kvadratisk rest
- Kvadratiska reciprocitetssatsen