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

Množina zbytkových tříd

Množinu všech zbytkových tříd pro dané $n$ značíme $ℤ_{n} = {[a]_{n} | a \in ℤ}$ ,kde $[a]_{n} = {b | b \equiv a (m o d n)}$ . Pro jednoduchost píšeme jen $ℤ_{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 mod n + b mod n) mod n = (a + b) mod n$
$(a mod n - b mod n) mod n = (a - b) mod n$
$(a mod n \cdot b mod n) mod n = (a \cdot b) mod 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.

$(ℤ_{n}, +)$ a $(ℤ_{p} ∖ {0}, \cdot)$ tvoří komutativní grupy pro kladné celé n a pro prvočíselné p. Například pro $ℤ_{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, 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

Externí odkazy

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

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.