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 , gdzie jest zadaną liczbą pierwszą.

Definicja[edytuj]

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]

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

  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.