Cesko.wiki Eulerovo kritérium
Author
Albert FloresEulerovo 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ů. +more 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}\equiv1\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.