Kryterium Eulera

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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

Definicja[edytuj | edytuj kod]

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

[1][2].

Jeśli jest nieresztą kwadratową modulo wtedy

[2].

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

[2].

Dowód[edytuj | edytuj kod]

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

Implikacja 1

Jeśli jest resztą kwadratową modulo to

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

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

Implikacja 2

Jeśli to jest resztą kwadratową modulo

Niech będzie pierwiastkiem pierwotnym modulo wtedy istnieje takie ż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

Przypisy[edytuj | edytuj kod]

  1. Wacław Marzantowicz, Piotr Zarzycki, Elementarna teoria liczb, Wydawnictwo Naukowe PWN, Warszawa 2012, ​ISBN 978-83-01-14855-3​, s. 37, Twierdzenie 8.6.
  2. a b c Wacław Marzantowicz, Piotr Zarzycki, Elementarna teoria liczb, Wydawnictwo Naukowe PWN, Warszawa 2012, ​ISBN 978-83-01-14855-3​, s. 67, Twierdzenie 14.2.