Kryterium Eulera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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]

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

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

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

Dowód[edytuj]

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

Z założenia istnieje taka liczba całkowita k, że , skąd po obustronnym podniesieniu do potęgi jest

,

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

Implikacja 2. jeśli , to a jest resztą kwadratową modulo p.

Niech będzie pierwiastkiem pierwotnym modulo p, wtedy istnieje takie q, że spełnione jest .

Z założenia jest , co jest prawdą dla każdej liczby całkowitej na mocy małego twierdzenia Fermata, stąd