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
- (ap){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 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 |
(ap)≡ap−12 mod p{displaystyle left({frac {a}{p}}right)equiv a^{frac {p-1}{2}} operatorname {mod} p}(Eulers kriterium)
- (a2p)=1{displaystyle left({frac {a^{2}}{p}}right)=1}
- (abp)=(ap)(bp){displaystyle left({frac {ab}{p}}right)=left({frac {a}{p}}right)left({frac {b}{p}}right)}
- a≡b mod p ⇒ (ap)=(bp){displaystyle aequiv b operatorname {mod} p Rightarrow left({frac {a}{p}}right)=left({frac {b}{p}}right)}
- (−1p)=(−1)p−12={1,om p≡1 mod 4−1,om p≡3 mod 4{displaystyle left({frac {-1}{p}}right)=(-1)^{frac {p-1}{2}}=left{{begin{matrix}1,&om pequiv 1 operatorname {mod} 4\-1,&om pequiv 3 operatorname {mod} 4end{matrix}}right.}
- (2p)=(−1)p2−18={1,om p≡1 el. 7 mod 8−1,om p≡3 el. 5 mod 8{displaystyle left({frac {2}{p}}right)=(-1)^{frac {p^{2}-1}{8}}=left{{begin{matrix}1,&om pequiv 1 el. 7 operatorname {mod} 8\-1,&om pequiv 3 el. 5 operatorname {mod} 8end{matrix}}right.}
Se även |
- Jacobisymbolen
- Kvadratisk rest
- Kvadratiska reciprocitetssatsen
