Kryterium Eulera

Kryterium Eulera jest używane w teorii liczb celem sprawdzenia, czy dana liczba całkowita jest resztą kwadratową modulo $p,$ gdzie $p$ jest zadaną nieparzystą liczbą pierwszą^[1]^[2].

Definicja

Niech $a$ będzie liczbą całkowitą, natomiast $p\geqslant 3$ liczbą pierwszą.

Kryterium Eulera można zapisać przy użyciu symbolu Legendre’a

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

^[1]^[2]^[3].

Czyli, rozpisując na przypadki, otrzymujemy:

jeśli liczba $a$ jest resztą kwadratową modulo $p,$ to

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

^[4],

jeśli liczba $a$ jest nieresztą kwadratową modulo $p,$ to

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

^[3],

liczba $a$ jest podzielna przez $p,$ wtedy i tylko wtedy, gdy

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

^[1].

Dowód

Dla $p|a$ teza kryterium jest oczywista. Niech więc $a\not \equiv 0{\pmod {p}}.$ Korzystając z małego twierdzenia Fermata otrzymujemy

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

Zatem $a^{\frac {p-1}{2}}\equiv \pm 1{\pmod {p}}.$

Jeśli $a$ jest resztą kwadratową modulo $p,$ to istnieje liczba $b$ taka, że $a\equiv b^{2}{\pmod {p}},$ stąd $a^{\frac {p-1}{2}}\equiv b^{p-1}\equiv 1{\pmod {p}}.$

Lemat. W zbiorze $\{1,2,\dots ,p-1\}$ jest tyle samo reszt co niereszt kwadratowych modulo $p.$

Dowód. Niech $s={\frac {p-1}{2}}.$ Zauważmy, że wśród $1^{2}{\text{(mod }}p),2^{2}{\text{(mod }}p),\dots ,s^{2}{\text{(mod }}p)$ jest $s$ różnych reszt kwadratowych. Jeśli dla pewnych $1\leqslant a<b\leqslant s$ zachodziłoby $a^{2}{\text{(mod }}p)=b^{2}{\text{(mod }}p),$ to otrzymalibyśmy $(b-a)(b+a)\equiv 0{\pmod {p}},$ co wobec narzuconych ograniczeń jest niemożliwe. Ponieważ każda niezerowa warstwa jest równa $a{\text{(mod }}p)$ lub $-a{\text{(mod }}p)$ dla pewnego $1\leqslant a\leqslant s,$ a takie dwie mają ten sam kwadrat, więc wskazaliśmy już wszystkie reszty kwadratowe. Niereszt kwadratowych jest więc $p-1-{\frac {p-1}{2}}={\frac {p-1}{2}}.$

Korzystając z lematu wiemy, że równanie $a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}$ ma rozwiązanie tylko wtedy, gdy $a$ jest resztą kwadratową. Zatem jeśli $a$ nie jest resztą kwadratową, to $a^{\frac {p-1}{2}}\not \equiv 1{\pmod {p}}\Rightarrow a^{\frac {p-1}{2}}\equiv -1{\pmod {p}},$ co wynika z równości uzyskanej poprzez małe twierdzenie Fermata^[1]^[2].

Przypisy

↑ ^a ^b ^c ^d AdamA. Neugebauer AdamA., Matematyka olimpijska. 1, Algebra i teoria liczb, wyd. 2, Kraków: Wydawnictwo Szkolne OMEGA, 2018, s. 203–204, ISBN 978-83-7267-710-5, OCLC 1055646686 [dostęp 2022-08-15] .
↑ ^a ^b ^c WładysławW. Narkiewicz WładysławW., Teoria liczb, wyd. 3, Warszawa: Wydawnictwo Naukowe PWN, 2003, s. 62, ISBN 83-01-14015-1, OCLC 749285993 [dostęp 2022-08-15] .
↑ ^a ^b Wacław Marzantowicz, Piotr Zarzycki, Elementarna teoria liczb, Wydawnictwo Naukowe PWN, Warszawa 2012, ISBN 978-83-01-14855-3, s. 67, Twierdzenie 14.2.
↑ Wacław Marzantowicz, Piotr Zarzycki, Elementarna teoria liczb, Wydawnictwo Naukowe PWN, Warszawa 2012, ISBN 978-83-01-14855-3, s. 37, Twierdzenie 8.6.

[:0-1] AdamA. Neugebauer AdamA., Matematyka olimpijska. 1, Algebra i teoria liczb, wyd. 2, Kraków: Wydawnictwo Szkolne OMEGA, 2018, s. 203–204, ISBN 978-83-7267-710-5, OCLC 1055646686 [dostęp 2022-08-15] .

[:1-2] WładysławW. Narkiewicz WładysławW., Teoria liczb, wyd. 3, Warszawa: Wydawnictwo Naukowe PWN, 2003, s. 62, ISBN 83-01-14015-1, OCLC 749285993 [dostęp 2022-08-15] .

[Leg-3] Wacław Marzantowicz, Piotr Zarzycki, Elementarna teoria liczb, Wydawnictwo Naukowe PWN, Warszawa 2012, ISBN 978-83-01-14855-3, s. 67, Twierdzenie 14.2.

[4] Wacław Marzantowicz, Piotr Zarzycki, Elementarna teoria liczb, Wydawnictwo Naukowe PWN, Warszawa 2012, ISBN 978-83-01-14855-3, s. 37, Twierdzenie 8.6.

[1]

[2]

[3]

[4]

Fahrer / Team für die Suche eingeben:

Fahrer / Team für die Suche eingeben:

Eisspeedway

Kryterium Eulera

Definicja

Dowód

Przypisy