Eulerovo kritérium

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

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

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

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

což lze přepsat jako

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

a první činitel je nulový, tedy

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 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

Čí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.