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 $\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. 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:

+	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

• Obrázky, zvuky či videa k tématu modulární aritmetika na Wikimedia Commons

Portály: Matematika