Na rozdíl od běžné aritmetiky je modulární aritmetika definována na nějaké konečné množině ℤn. Tato množina vznikne ze ℤ tak, že jsou všechna čísla se stejným zbytkem po dělení číslem (zbytková třída) brána jako kongruentní a ztotožněna s jediným reprezentantem. Taková množina se pak nazývá množina zbytkových tříd.
Zbytková třída Zbytkovou třídou modulo n rozumíme množinu všech celých čísel, která při dělení přirozeným číslem n dávají stejný zbytek. Tuto množinu pak můžeme chápat jako jeden celek a celá čísla, která obsahuje, již dál nerozlišovat. Například jedna ze zbytkových tříd modulo 10 je tvořena množinou , jiná zbytková třída (rovněž) modulo 10 obsahuje např. prvky .
Číselné kongruence modulo n Pro libovolné definujme relaci takto: . Čísla se nazývají kongruentní modulo n a relace se nazývá číselná kongruence modulo n. Značíme . Relace je reflexivní, symetrická a transitivní, je tedy relací ekvivalence. Znaménko tedy můžeme používat podobně jako znaménko =. Rovnosti v modulární aritmetice se obvykle zapisují jako kongruence a značí se trojčárkou: a + b ≡ b + a (mod n)
Obecně vzato, rozklad, který kongruence na vytváří, má n tříd, pro které platí:
Množina zbytkových tříd Množinu všech zbytkových tříd pro dané značíme ,kde . Pro jednoduchost píšeme jen .
Základní vlastnosti modulární aritmetiky Zavedená ekvivalence mezi prvky tvoří na okruhu (ℤ,+,·,0,1) kongruenci, tedy ∀a,b,n∈ℤ
Proto je možné při výpočtech vzájemně zaměňovat prvky ve stejných třídách. Pro zjednodušení se nejčastěji používá vždy nejmenší nezáporné číslo.
a tvoří komutativní grupy pro kladné celé n a pro prvočíselné p. Například pro mají Cayleyovy tabulky tvar: + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 ⋅ 1 2 3 4 1 1 2 3 4 2 2 4 1 3 3 3 1 4 2 4 4 3 2 1
Další operace Na ℤn lze přirozeně dodefinovat i další operace: opačné číslo, jako inverzní operaci vzhledem ke sčítání odčítání, jako součet s opačným číslem mocnění, jako iterace násobení odmocnina a logaritmus, jako inverzní operace k mocnění
Pokud je n prvočíslo, pak ℤn tvoří těleso, protože pro každý nenulový prvek existuje inverzní prvek (vzhledem k násobení). Dělení se pak definuje jako násobení inverzním prvkem.
Operace dělení a diskrétní logaritmus v modulární matematice se nechovají stejně jako v klasické aritmetice a tedy není možné jejich výsledky přímo převést do ℤn jako u sčítání a násobení.
Aplikace Lidem je přirozenější klasická aritmetika, avšak modulární aritmetika má řadu výhod. Díky tomu, že je zde množina čísel konečná, jsou běžné operace jednodušší, rychlejší a potřebují konstantní množství paměti. Toho se využívá v počítačích, kde bývá typ „celých čísel“ obvykle implementován v modulární aritmetice (nejčastěji ).
Na druhou stranu pro některé funkce není znám efektivní algoritmus (diskrétní logaritmus, faktorizace), čehož se často využívá v kryptografii.
Odkazy
Literatura HORT, Daniel a RACHŮNEK, Jiří. Algebra I. 1. vyd. Olomouc: Univerzita Palackého, 2003. ISBN 80-244-0631-4. Dostupné po přihlášení. RACHŮNEK, Jiří. Grupy a okruhy. 1. vyd. Olomouc: Univerzita Palackého, 2005. ISBN 80-244-0998-4. Související články zbytek po dělení teorie čísel okruh (algebra)
Externí odkazy
Kategorie:Aritmetika Kategorie:Algebra