Kryterium Eulera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Kryterium Eulera jest używane w teorii liczb celem sprawdzenia czy dana liczba całkowita jest resztą kwadratową modulo p, gdzie p jest zadaną liczbą pierwszą.

Definicja[edytuj | edytuj kod]

Jeśli p jest nieparzystą liczbą pierwszą i a daną liczbą całkowitą, to a jest resztą kwadratową modulo p wtedy i tylko wtedy, gdy

a^{\frac{p-1}{2}} \equiv 1 \pmod p

Jeśli a jest nieresztą kwadratową modulo p wtedy

a^{\frac{p-1}{2}} \equiv -1 \pmod p

Równoważnie kryterium Eulera można zapisać przy użyciu symbolu Legendre'a

\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p

Dowód[edytuj | edytuj kod]

Kryterium opiera się na równoważności, więc przeprowadzimy dowody dwóch implikacji.

Implikacja 1. jeśli a jest resztą kwadratową modulo p, to a^{\frac{p-1}{2}} \equiv 1 \pmod p

Z założenia istnieje taka liczba całkowita k, że a \equiv k^2 \pmod p, skąd po obustronnym podniesieniu do potęgi \frac{p-1}{2} jest

a^{\frac{p-1}{2}} \equiv k^{p-1} \equiv 1 \pmod p,

gdzie drugie przystawanie ma miejsce na podstawie małego twierdzenia Fermata dla dowolnego k.

Implikacja 2. jeśli a^{\frac{p-1}{2}} \equiv 1 \pmod p, to a jest resztą kwadratową modulo p.

Niech t będzie pierwiastkiem pierwotnym modulo p, wtedy istnieje takie q, że spełnione jest t^q \equiv a \pmod p.

Z założenia jest (t^{q/2})^{p-1} \equiv 1 \pmod p, co jest prawdą dla każdej liczby całkowitej k = t^{q/2} na mocy małego twierdzenia Fermata, stąd k^2 = t^q \equiv a \pmod p