Kryterium Eulera jest używane w teorii liczb celem sprawdzenia, czy dana liczba całkowita jest resztą kwadratową modulo gdzie jest zadaną nieparzystą liczbą pierwszą.
Definicja Niech będzie liczbą całkowitą, natomiast liczbą pierwszą.
Kryterium Eulera można zapisać przy użyciu symbolu Legendre’a Wacław Marzantowicz, Piotr Zarzycki, Elementarna teoria liczb, Wydawnictwo Naukowe PWN, Warszawa 2012, , s. 67, Twierdzenie 14.2..
Czyli, rozpisując na przypadki, otrzymujemy: jeśli liczba jest resztą kwadratową modulo to Wacław Marzantowicz, Piotr Zarzycki, Elementarna teoria liczb, Wydawnictwo Naukowe PWN, Warszawa 2012, , s. 37, Twierdzenie 8.6.,
jeśli liczba jest nieresztą kwadratową modulo to ,
liczba jest podzielna przez wtedy i tylko wtedy, gdy .
Dowód Dla teza kryterium jest oczywista. Niech więc Korzystając z małego twierdzenia Fermata otrzymujemy
Zatem
Jeśli jest resztą kwadratową modulo to istnieje liczba taka, że stąd
Lemat. W zbiorze jest tyle samo reszt co niereszt kwadratowych modulo
Dowód. Niech Zauważmy, że wśród jest różnych reszt kwadratowych. Jeśli dla pewnych zachodziłoby to otrzymalibyśmy co wobec narzuconych ograniczeń jest niemożliwe. Ponieważ każda niezerowa warstwa jest równa lub dla pewnego a takie dwie mają ten sam kwadrat, więc wskazaliśmy już wszystkie reszty kwadratowe. Niereszt kwadratowych jest więc
Korzystając z lematu wiemy, że równanie ma rozwiązanie tylko wtedy, gdy jest resztą kwadratową. Zatem jeśli nie jest resztą kwadratową, to co wynika z równości uzyskanej poprzez małe twierdzenie Fermata.
Przypisy
Kategoria:Twierdzenia teorii liczb Kategoria:Teoria liczb