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}({\pmod {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^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&{\text{ existuje-li celé číslo }}x{\text{ takové, že }}a\equiv x^{2}{\pmod {p}}\\-1{\pmod {p}}&{\text{ neexistuje-li takové celé číslo.}}\end{cases}}$

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}{\pmod {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{\pmod {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{\pmod {p}},$

což lze přepsat jako

$\left(a^{\tfrac {p-1}{2}}-1\right)\left(a^{\tfrac {p-1}{2}}+1\right)\equiv 0{\pmod {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^{\tfrac {p-1}{2}}\equiv {(x^{2})}^{\tfrac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}.$

a první činitel je nulový, tedy

$a^{\tfrac {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^{\tfrac {p-1}{2}}\equiv -1$

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

Reference

V tomto článku byl použit překlad textu z článku Euler's criterion na anglické Wikipedii.