Kvadratický zbytek

Kvadratický zbytek je pojem z oblasti matematiky, přesněji z oblasti teorie čísel. Celé číslo se nazývá kvadratický zbytek modulo celé číslo , pokud jsou tato čísla nesoudělná a existuje celé číslo splňující kongruenci:

což lze ekvivalentně vyjádřit tak, že existuje celé číslo , pro které platí:

Pokud požadované číslo neexistuje, nazývá se číslo kvadratický nezbytek.

Alternativně lze definovat kvadratický zbytek modulo jako číslo kongruentní modulo se čtvercovým číslem.

Příklad

Následující tabulka shrnuje druhé mocniny pro všech šest zbytkových tříd modulo 6.

0000
1011
2044
3093
4164
5251

Protože čísla 0,2,3 a 4 jsou soudělná s 6, nejsou ani zbytky, ani nezbytky. Číslo jedna je kvadratickým zbytkem ( a ) a číslo 5 je kvadratickým nezbytkem, neboť neexistuje žádné celé číslo, jehož druhá mocnina by dávala po dělení šesti se zbytkem zbytek 5.

Legendreův a Jacobiho symbol

Modulo prvočíslo klasifikuje čísla na čísla soudělná, zbytky a nezbytky Legendreův symbol, jehož hodnotu je možné rychle počítat Eulerovým kritériem. Není-li modulo prvočíslem, pak Jacobiho symbol, rozšíření Legendreova symbolu na složené moduly, poskytuje jen částečnou informaci.

Odkazy

Literatura

  • VINOGRADOV, Ivan Matvejevič. Základy theorie čísel. Praha: Nakladatelství Československé akademie věd, 1953. Kapitola Kongruence druhého stupně. 

Reference

V tomto článku byl použit překlad textu z článku Quadratischer Rest na německé Wikipedii.