Eulerovo kritérium

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

${\displaystyle 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:

${\displaystyle \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ě ${\displaystyle k}$ může mít nejvýše ${\displaystyle k}$ kořenů. Tedy v tomto případě má rovnice ${\displaystyle x^{2}\equiv a{\pmod {p}}}$ nejvýše dva kořeny pro každé ${\displaystyle a}$. Na druhou stranu, každé ${\displaystyle x}$ (kromě nuly) může svoji druhou mocninu sdílet jen s jedním jiným ${\displaystyle x}$, což znamená, že kvadratických zbytků je nejméně ${\displaystyle (p-1)/2}$.

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

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

což lze přepsat jako

${\displaystyle \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 ${\displaystyle p}$ tvoří těleso, jeden z činitelů výrazu výše musí být roven nule. Pokud je ${\displaystyle a}$ kvadratickým zbytkem, tedy například ${\displaystyle a\equiv x^{2}}$, pak

${\displaystyle 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

${\displaystyle 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 ${\displaystyle (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

${\displaystyle 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.