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(\mathrm{mod}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}mod6$
0	Šablona:00	0
1	Šablona:01	1
2	Šablona:04	4
3	Šablona: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

• Šablona:Citace monografie