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	00	0
1	01	1
2	04	4
3	09	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

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.