Symbol Legendre'a

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Symbol Legendre'a to funkcja \left( \frac a p \right) (p musi być liczbą pierwszą większą od 2) zwracająca:

0, jeśli a jest wielokrotnością p
1, jeśli istnieje takie b, że b^2=a \mod p
-1, jeśli nie istnieje żadne b, żeby b^2=a \mod p

Lub w terminologii teorii grup:

0, jeśli a nie należy do Z_p^*
1, jeśli a jest resztą kwadratową w Z_p^*
-1, jeśli a nie jest resztą kwadratową w Z_p^*

Funkcję tę można łatwo obliczać:

\left( \frac a p \right) = a^{\frac {p-1} 2} \mod p

Ważniejsze właściwości:

Jeśli a=b \mod p, to \left( \frac a p \right) = \left( \frac b p \right)
\left( \frac 1 p \right) = 1^{\frac {p-1} 2} \mod p = 1
\left( \frac {-1} p \right) = (-1)^{\frac {p-1} 2} \mod p = 1, jeśli p = 1 \mod 4
\left( \frac {-1} p \right) = (-1)^{\frac {p-1} 2} \mod p = -1, jeśli p = 3 \mod 4
\left( \frac a p \right) \left( \frac b p \right) = \left( \frac {ab} p \right)

Najważniejszym wzorem jest jednak prawo wzajemności reszt kwadratowych

\left( \frac q p \right) = \left( \frac p q \right) (-1)^{\frac {(p-1)(q-1)} 4}, dla p i q będących dowolnymi różnymi nieparzystymi liczbami pierwszymi

Co innymi słowy znaczy:

\left( \frac q p \right) = -\left( \frac p q \right), jeśli p i q są postaci 4k+3
\left( \frac q p \right) = \left( \frac p q \right), jeśli przynajmniej jedna z nich nie jest

Uogólnieniem symbolu Legendre'a na nieparzyste liczby niekoniecznie pierwsze jest symbol Jacobiego.

Linki zewnętrzne[edytuj | edytuj kod]

Przypisy