Slovník | Vyhledávání | Mapa webu
 
Základy informatiky pro biologyTeoretické základy informatiky Teorie čísel Modulární aritmetika

Logo Matematická biologie

Modulární aritmetika

Obecnější a zajímavější než zkoumat dělitelnost čísel, je zajímavé zkoumat zbytek při dělení. Na rozdíl od běžné aritmetiky je modulární aritmetika definována na konečné množině Zn. Ta vznikne ze Z tak, že jsou ztotožněna čísla se stejným zbytkem po dělení číslem n. Někdy se této aritmetice říká aritmetika zbytkových tříd.

Definice 1.7: Uvažujme celá čísla a a b a přirozené číslo n (a,b Z, nN) a označme symbolem "a mob n" zbytek při dělení čísla a číslem n.

Příklad: V programovacích jazycích se pro výpočet zbytku po dělení používá právě operace mod. Například:

25 mod 4 = 1 - protože 25 / 4 = 6 a zbytek je 1

19 mod 5 = 4 - protože 19 = 3 * 5 + 4

24 mod 5 = 4

Definice 1.8: Řekneme, že a je kongruentní s b modulo n, pokud a mod n = b mod n. Jinými slovy, zbytek při dělení a|n a b|n je tentýž. Píšeme pak a ≡ b (mod n).

Dále pak platí že: a ≡ b (mod n)n dělí (a-b)

Příklad:          

53 mod 7 = 4

53 ≡ 4 (mod 7)

Příklad: Všem známé užití modulární aritmetiky je například ve 12-hodinovém určování času. Den je rozdělen na dva 12-ti hodinové úseky. Jestliže je nyní čas 7:00, pak o 8 hodin později to bude 3:00. Obvyklým sčítáním by nám ale vyšlo, že by mělo být 7 + 8 = 15 hodin. Vzhledem ale k tomu že je k dispozici pouze 12 hodinových úseků, tak se čas vždy ve 12 hodin začne počítat od začátku. Vzhledem k tomu, že se hodiny začnou počítat od začátku vždy ve 12 hodin, tak v tomto případě můžeme mluvit o aritmetice modulo 12. Díky tomu se můžete u modulární aritmetiky setkat s označením Clock arithmetic.

Příklad: Jaké další příklady modulárních aritmetik z běžného života znáte?

hodiny, týdny, roky ... 14 ≡ 2 (mod 12), 730 ≡ 0 (mod 365)

Níže následuje seznam základních vlastností kongurence. Pro všechna a, b, a1, b1, cZ platí:

  1. a ≡ b (mod n) právě tehdy, když zbytek po dělení čísel a i b číslem n je stejný
  2. a ≡ a (mod n) pro  - reflexivita
  3. Jestliže a ≡ b (mod n) → b ≡ a (mod n) - symetrie
  4. Jestliže a ≡ b (mod n) a b ≡ c (mod n), potom a ≡ c (mod n) - tranzitivita
  5. Jestliže a ≡ a1 (mod n) a b ≡ b1 (mod n), potom a + b ≡ a1 + b1 (mod n)

Z předchozího vidíme, že relace kongruence je ekvivalencí, protože je reflexivní, symetrická a tranzitivní. Třída ekvivalence celých čísel a je množina všech celých čísel kongruentních s a modulo n. Vidíme, že pro dané n relace kongruence a modulo n dělí množinu Z na třídy ekvivalence, na tzv. zbytkové třídy modulo n.

Definice 1.9: Nechť je dáno n > 0. Pro každé celé číslo a definujeme [a]n = {x | x ≡ a (mod n)} jako množinu celých čísel kongruentních a modulo n a nazveme ji množinou zbytkových tříd modulo n - značíme Zn.

Příklad: Každé číslo ze Zn reprezentuje zbytkovou třídu. Nechť n = 7, zbytkové třídy modulo 7 označme jako [0]7, [1]7,..., [6]7, pak [2]7 = {..., -12, -5, 2, 9, 16, ...}.

Definice 1.10: Nechť aZn. Multiplikativní inverzní prvek k prvku a mod n je číslo xZn takové, že a*x ≡ 1 (mod n). Pokud takové x existuje, pak je jednoznačné. Inverzní prvek k a mod n označujeme a-1.

Definice 1.11: Nechť a Zn. Dělení čísla a číslem b modulo n je definováno jako součin a * b-1  modulo n je definováno jen tehdy, je-li b invertovatelné mod n.

Definice 1.12: Nechť aZn. Aditivní opačný prvek k prvku a modulo n je číslo x ∈ Zn takové, že a + x ≡ 0 (mod n). Pokud takové x existuje, je jednoznačné. Opačný prvek k a modulo n budeme označovat −x.

Pro určení toho, zda k danému a ∈ Zn existuje inverzní prvek využijeme faktu, že číslo a je invertovatelné právě tehdy když NSD(a,n) = 1.

Příklad: Nechť n = 9, Zn = {0, 1, 2, 3, 4, 5, 6, 7, 8}. Určete invertovatelné prvky.

Řešení

Invertovatelné jsou prvky 1, 2, 4, 5, 7, 8, např. 5−1 = 2, protože 5 · 2 ≡ 1 (mod 9)

Příklad: Kolik je 38 (mod 7)?

Řešení

a) 38 34 * 34 (81 (mod 7)) * (81 (mod 7)) 4*4 = 16 2 (mod 7)

b) 38 = 6561 2 (mod 7) protože 6561 = 937 * 7 + 2

Úlohy k procvičení

 
vytvořil Institut biostatistiky a analýz Masarykovy univerzity | | zpětné odkazy | validní XHTML 1.0 Strict