Legendrov simbol

Legendrov simból [ležándrov ~] je v teoriji števil simbol, ki se uporablja pri faktorizaciji in kvadratnih ostankih. Simbol je uvedel Adrien-Marie Legendre.

Definicija

Legendrov simbol je poseben primer Jacobijevega simbola. Odvisen je od tega ali za dve celi števili p in a velja:

• $a\equiv 0(\mathrm{mod}p)$ (oziroma p deli a), ali
• $a\equiv x^2(\mathrm{mod}p)$ (oziroma a je kvadrat mod p) ali
• $a\equiv ̸x^2(\mathrm{mod}p)$ (oziroma a ni kvadrat mod p).

Če je p liho praštevilo in a celo število je Legendrov simbol:

$\left(\frac{a}{p}\right)=\{\begin{array}{cc}0;& p|a\\ 1;& \mathrm{z}\mathrm{a}\mathrm{t}\mathrm{a}\mathrm{k}k\mathrm{d}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{l}\mathrm{j}\mathrm{a}{k}^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)\\ -1;& \mathrm{s}\mathrm{i}\mathrm{c}\mathrm{e}\mathrm{r}\end{array}.$

Simbol se označuje tudi kot:

$(a/p)\mathrm{a}\mathrm{l}\mathrm{i}L(a,p).$

Značilnosti Legendrovega simbola

Legendrov simbol ima več uporabnih značilnosti, ki pospešijo računanje:

1. $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ (je popolnoma multiplikativna funkcija za zgornji argument)
2. Če je a ≡ b (mod p), potem velja $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$
3. $\left(\frac{1}{p}\right)=1$
4. $\left(\frac{-1}{p}\right)=(-1{)}^{(p-1)/2}$, oziroma = 1, če je p ≡ 1 (mod 4) in = −1, če je p ≡ 3 (mod 4)
5. $\left(\frac{2}{p}\right)=(-1{)}^{(p^2-1)/8}$, oziroma = 1, če je p ≡ 1 ali 7 (mod 8) in = −1, če je p ≡ 3 ali 5 (mod 8)
6. Za liho praštevilo q velja $\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)(-1{)}^{((p-1)/2)((q-1)/2)}$

Zadnja značilnost je znana kot kvadratni recipročnostni zakon. Značilnosti 4 in 5 sta tradicionalno znani kot dodatka h kvadratni recipročnosti. Dokazati ju je moč z Gaussovo lemo.

Legendrov simbol je povezan z Eulerjevim kriterijem. Euler je dokazal, da velja:

$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}(\mathrm{mod}p).$

Legendrov simbol je tudi Dirichletov karakter.

Sorodne funkcije

Jacobijev simbol je posplošitev Legendrovega simbola, ki dovoljuje sestavljena spodnja števila. S posplošitvijo je moč uspešno računati Legendrove simbole.

Druga posplošitev je Kroneckerjev simbol.