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ą.

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}}$.

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}}$,

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

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

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

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

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.