Eulerovo kritérium

Eulerovo kritérium je matematické tvrzení z oboru teorie čísel, které poskytuje algoritmus, jak rychle rozpoznat, zda je zadané celé číslo $a$ kvadratickým zbytkem modulo zadané prvočíslo $p$, tedy zda existuje celé číslo $x$, že $a\equiv x^2((\mathrm{mod}p))$. Může být vysloveno v následujícím znění: Je-li $p$ liché prvočíslo a $a$ je celé číslo nesoudělné s $p$, pak

$a^{\frac{p-1}{2}}\equiv \{\begin{array}{cc}1(\mathrm{mod}p)& \text{ existuje-li celé číslo }x\text{ takové, že }a\equiv x^2(\mathrm{mod}p)\\ -1(\mathrm{mod}p)& \text{ neexistuje-li takové celé číslo.}\end{array}$

Jiným způsobem vyjádření téhož je rovnost s patřičným Legendreovým symbolem:

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

Tvrzení je pojmenováno po Leonhardu Eulerovi, který jej popsal v roce 1748.

Důkaz

Důkaz využívá znalosti, že zbytkové třídy modulo prvočíslo tvoří konečné těleso. V takové situaci platí Langrangeova věta, která říká, že mnohočlen stupně $k$ může mít nejvýše $k$ kořenů. Tedy v tomto případě má rovnice $x^2\equiv a(\mathrm{mod}p)$ nejvýše dva kořeny pro každé $a$. Na druhou stranu, každé $x$ (kromě nuly) může svoji druhou mocninu sdílet jen s jedním jiným $x$, což znamená, že kvadratických zbytků je nejméně $(p-1)/2$.

Protože je $a$ nesoudělné s $p$, platí podle Malé Fermatovy věty kongruence

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

což lze přepsat jako

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

Protože celá čísla modulo $p$ tvoří těleso, jeden z činitelů výrazu výše musí být roven nule. Pokud je $a$ kvadratickým zbytkem, tedy například $a\equiv x^2$, pak

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

a první činitel je nulový, tedy

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

Na první činitel lze opět použít Lagrangeovu větu, z které tentokrát plyne, že první činitel může být nulový pouze pro $(p-1)/2$ hodnot. Ale to je právě maximální možný počet kvadratických zbytků: Pro nezbytky tedy musí být nulový druhý činitel, tedy

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

Čímž je kritérium dokázáno.