Kvadratický zbytek

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

${\displaystyle a\equiv x^{2}{\pmod {m}}}$

což lze ekvivalentně vyjádřit tak, že existuje celé číslo ${\displaystyle t}$, pro které platí:

${\displaystyle a=x^{2}+t\cdot m}$

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

Alternativně lze definovat kvadratický zbytek modulo ${\displaystyle m}$ jako číslo kongruentní modulo ${\displaystyle m}$ se čtvercovým číslem.

Příklad

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

${\displaystyle x}$	${\displaystyle x^{2}}$	${\displaystyle 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 (${\displaystyle 1^{2}\equiv 1}$ a ${\displaystyle 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.