Modulární aritmetika

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 n (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. +more Například jedna ze zbytkových tříd modulo 10 je tvořena množinou \{2, 12, 22, 32, . \}, jiná zbytková třída (rovněž) modulo 10 obsahuje např. prvky \{7, 17, 27, -3, -13, -1234567893, 1147, . \}.

Číselné kongruence modulo n

Pro libovolné n\in \mathbb N, a,b \in \mathbb Z definujme relaci \phi_n takto: (a,b)\in\phi_n \Leftrightarrow n|a-b. Čísla a,b se nazývají kongruentní modulo n a relace \phi_n se nazývá číselná kongruence modulo n. +more Značíme a\equiv b(mod\ n). Relace \phi_n je reflexivní, symetrická a transitivní, je tedy relací ekvivalence. Znaménko \equiv 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 \phi_n na \mathbb Z vytváří má n tříd, pro které platí: [0]_{\phi_n}=\{k\cdot n|k\in \mathbb Z\}, [1]_{\phi_n}=\{1+k\cdot n|k\in \mathbb Z\},\dots , [n-1]_{\phi_n}=\{(n-1)+k\cdot n|k\in \mathbb Z\}.

Množina zbytkových tříd

Množinu všech zbytkových tříd pro dané n značíme \mathbb Z_n=\{[a]_n|a\in \mathbb Z\} ,kde [a]_n=\{b|b\equiv a(mod\ n)\}. Pro jednoduchost píšeme jen \mathbb Z_n=\{0,1,\dots ,n-1\}.

Základní vlastnosti modulární aritmetiky

Zavedená ekvivalence mezi prvky tvoří na okruhu (ℤ,+,·,0,1) kongruenci, tedy ∀a,b,n∈ℤ * (a\;\bmod\;n + b\;\bmod\;n)\;\bmod\;n =(a+b)\;\bmod\;n * (a\;\bmod\;n - b\;\bmod\;n)\;\bmod\;n =(a-b)\;\bmod\;n * (a\;\bmod\;n \cdot b\;\bmod\;n)\;\bmod\;n =(a\cdot b)\;\bmod\;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.

(\mathbb Z_n,+) a (\mathbb Z_p \smallsetminus \{0\},\cdot ) tvoří komutativní grupy pro kladné celé n a pro prvočíselné p. Například pro \mathbb Z_5 mají Cayleyovy tabulky tvar:

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. +more 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 n=2^{32}).

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 D., Rachůnek J.; Algebra 1. UP Olomouc, 2003 * Rachůnek J.; Grupy a okruhy, UP Olomouc, 2005

Související články

zbytek po dělení * teorie čísel * okruh (algebra)

Externí odkazy

Kategorie:Aritmetika Kategorie:Algebra