Kryterium Eulera

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

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

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

${\displaystyle \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 ${\displaystyle a}$ jest resztą kwadratową modulo ${\displaystyle p,}$ to

${\displaystyle a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}$^[4],

• jeśli liczba ${\displaystyle a}$ jest nieresztą kwadratową modulo ${\displaystyle p,}$ to

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$^[3],

• liczba ${\displaystyle a}$ jest podzielna przez ${\displaystyle p,}$ wtedy i tylko wtedy, gdy

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

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

${\displaystyle 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 ${\displaystyle a^{\frac {p-1}{2}}\equiv \pm 1{\pmod {p}}.}$

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

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

Dowód. Niech ${\displaystyle s={\frac {p-1}{2}}.}$ Zauważmy, że wśród ${\displaystyle 1^{2}{\text{(mod }}p),2^{2}{\text{(mod }}p),\dots ,s^{2}{\text{(mod }}p)}$ jest ${\displaystyle s}$ różnych reszt kwadratowych. Jeśli dla pewnych ${\displaystyle 1\leqslant a<b\leqslant s}$ zachodziłoby ${\displaystyle a^{2}{\text{(mod }}p)=b^{2}{\text{(mod }}p),}$ to otrzymalibyśmy ${\displaystyle (b-a)(b+a)\equiv 0{\pmod {p}},}$ co wobec narzuconych ograniczeń jest niemożliwe. Ponieważ każda niezerowa warstwa jest równa ${\displaystyle a{\text{(mod }}p)}$ lub ${\displaystyle -a{\text{(mod }}p)}$ dla pewnego ${\displaystyle 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 ${\displaystyle p-1-{\frac {p-1}{2}}={\frac {p-1}{2}}.}$

Korzystając z lematu wiemy, że równanie ${\displaystyle a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}$ ma rozwiązanie tylko wtedy, gdy ${\displaystyle a}$ jest resztą kwadratową. Zatem jeśli ${\displaystyle a}$ nie jest resztą kwadratową, to ${\displaystyle 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].