Modulární aritmetika

obor matematiky a algebraický systém zabývající se operacemi s čísly z konečné množiny tvořené zbytky po dělení daným fixním číslem

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

editovat

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

editovat

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

editovat

Množinu všech zbytkových tříd pro dané   značíme   ,kde  . Pro jednoduchost píšeme jen  .

Základní vlastnosti modulární aritmetiky

editovat

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

editovat

Na ℤn lze přirozeně dodefinovat i další operace:

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

editovat

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.

Literatura

editovat
  • Hort D., Rachůnek J.; Algebra 1. UP Olomouc, 2003
  • Rachůnek J.; Grupy a okruhy, UP Olomouc, 2005

Související články

editovat

Externí odkazy

editovat