Kvadratický zbytek

Kvadratický zbytek je pojem z oblasti matematiky, přesněji z oblasti teorie čísel. Celé číslo a se nazývá kvadratický zbytek modulo celé číslo m, pokud jsou tato čísla nesoudělná a existuje celé číslo x splňující kongruenci: :a \equiv x^2 \pmod m což lze ekvivalentně vyjádřit tak, že existuje celé číslo t, pro které platí: :a = x^2 + t\cdot m

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

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

Příklad

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

x	x^2	x^2 \bmod 6
0	0	0
1	1	1
2	4	4
3	9	3
4	16	4
5	25	1

Protože čísla 0,2,3 a 4 jsou soudělná s 6, nejsou ani zbytky, ani nezbytky. Číslo jedna je kvadratickým zbytkem (1^2\equiv 1 a 5^2\equiv 1) 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

Reference

Kategorie:Teorie čísel