Legendrov simbol

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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[uredi | uredi kodo]

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

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

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

 \left( {a\over p}\right) = \left\{\begin{matrix} 
0;      &  p \vert a \\ 
1;      &  \mathrm{za \ tak \ } k \ \mathrm{da \ velja \ } k^{2} \equiv a\ (\mathrm{mod \ } p) \\
-1;     &  \mathrm{sicer} \end{matrix}\right. \!\, .

Simbol se označuje tudi kot:

(a/p) \ \mathrm{ali \ } L(a,p) \!\, .

Značilnosti Legendrovega simbola[uredi | uredi kodo]

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 ab (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 kvadratični reciprocitetni zakon. Značilnosti 4 in 5 sta tradicionalno znani kot dodatka k 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}\pmod p \!\, .

Legendrov simbol je tudi Dirichletov karakter.

Sorodne funkcije[uredi | uredi kodo]

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.