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, n ∈ N) 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, c ∈ Z platí:
- a ≡ b (mod n) právě tehdy, když zbytek po dělení čísel a i b číslem n je stejný
-
a ≡ a (mod n) pro
- reflexivita
- Jestliže a ≡ b (mod n) → b ≡ a (mod n) - symetrie
- Jestliže a ≡ b (mod n) a b ≡ c (mod n), potom a ≡ c (mod n) - tranzitivita
- 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ť a ∈ Zn. Multiplikativní inverzní prvek k prvku a mod n je číslo x ∈ Zn 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ť a ∈ Zn. 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.
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)?
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
