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. 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 ${\varphi }_n$ takto: $(a,b)\in {\varphi }_n\iff n|a-b$. Čísla $a,b$ se nazývají kongruentní modulo n a relace ${\varphi }_n$ se nazývá číselná kongruence modulo n. Značíme $a\equiv b(modn)$. Relace ${\varphi }_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 ${\varphi }_n$ na $\mathbb{Z}$ vytváří má n tříd, pro které platí: $[0{]}_{{\varphi }_n}=\{k\cdot n|k\in \mathbb{Z}\},[1{]}_{{\varphi }_n}=\{1+k\cdot n|k\in \mathbb{Z}\},\dots ,[n-1{]}_{{\varphi }_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(modn)\}$. 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∈ℤ

• $(amodn+bmodn)modn=(a+b)modn$
• $(amodn-bmodn)modn=(a-b)modn$
• $(amodn\cdot bmodn)modn=(a\cdot b)modn$

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\setminus \{0\},\cdot )$ tvoří komutativní grupy pro kladné celé n a pro prvočíselné p. Například pro ${\mathbb{Z}}_5$ 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 $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

• Šablona:Commonscat