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⩾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}}(\mathrm{mod}p)$.

Czyli, rozpisując na przypadki, otrzymujemy:

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

$a^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$,

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

$a^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p)$,

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

$a^{\frac{p-1}{2}}\equiv 0(\mathrm{mod}p)$.

Dowód

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

$0\equiv a^{p-1}-1\equiv (a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1)(\mathrm{mod}p).$

Zatem $a^{\frac{p-1}{2}}\equiv \pm 1(\mathrm{mod}p).$

Jeśli $a$ jest resztą kwadratową modulo $p,$ to istnieje liczba $b$ taka, że $a\equiv b^2(\mathrm{mod}p),$ stąd $a^{\frac{p-1}{2}}\equiv b^{p-1}\equiv 1(\mathrm{mod}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⩽a<b⩽s$ zachodziłoby $a^2\text{(mod }p)=b^2\text{(mod }p),$ to otrzymalibyśmy $(b-a)(b+a)\equiv 0(\mathrm{mod}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⩽a⩽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(\mathrm{mod}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}}\equiv ̸1(\mathrm{mod}p)\Rightarrow a^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p),$ co wynika z równości uzyskanej poprzez małe twierdzenie Fermata.