A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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.
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk