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řídaEditovat

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 nEditovat

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řídEditovat

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


Základní vlastnosti modulární aritmetikyEditovat

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ší operaceEditovat

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

Pokud je   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í.

AplikaceEditovat

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.

OdkazyEditovat

LiteraturaEditovat

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

Související článkyEditovat