Hlavní obsah
Informatika
Kurz: Informatika > Kapitola 1
Lekce 5: Modulární aritmetika- Co je to modulární aritmetika?
- Operátor modulo
- Výzva Modulo
- Kongruence modulo
- Kongruence modulo
- Relace ekvivalence
- Věta o dělení se zbytkem
- Modulární sčítání a odčítání
- Modulární sčítání
- Výzva modulo (sčítání a odčítání)
- Modulární násobení
- Modulární násobení
- Modulární mocnění
- Rychlé modulární umocňování
- Rychlé modulární umocňování
- Modulární inverze
- Euklidův algoritmus
Co je to modulární aritmetika?
Úvod do modulární aritmetiky
Když dělíme dvě celá čísla, dostaneme rovnici, která vypadá nějak takto:
Někdy nás zajímá jen jaký je zbytek po dělení čísla číslem .
Pro tyto případy je operátor zvaný modulo (zkráceně „mod“).
Pro tyto případy je operátor zvaný modulo (zkráceně „mod“).
Použitím stejných , , a jako výše, dostaneme:
Čteme jako modulo je rovno , kde je je někdy označováno jako modulus.
Například:
Znázornění operace modulo pomocí hodin.
Všimni si, co se děje, když zvyšujeme čísla o 1 a pak je dělíme 3.
Zbytek začíná na 0 a pokaždé se zvětší se o 1, dokud nedosáhne čísla o jedno menší, než je číslo, kterým dělíme. Poté se posloupnost čísel opakuje.
Když jsme si tohoto všimli, můžeme si operátor modulo znázornit pomocí kružnice.
Nahoru na kružnici napíšeme 0 a pokračujeme psaním celých čísel 1, 2, … až do čísla o jedno menší, než je modulus.
Například hodiny s 12 vyměněnou za 0 jsou kružnicí pro modulo 12.
Abychom nalezli držme se těchto kroků:
- Sestavme hodiny pro velikost
- Začněme na 0 a a pokračujme dále po
krocích - Kam se dostaneme, to je výsledek.
(Je-li číslo kladné, postupujeme ve směru hodinových ručiček, je-li záporné postupujeme proti směru hodinových ručiček.)
Příklady
Pro modulus = 4 vytvoříme hodiny s čísly 0, 1, 2, 3.
Začneme na 0 a pokračujeme přes 8 čísel ve směru hodinových ručiček v posloupnosti 1, 2, 3, 0, 1, 2, 3, 0.
Začneme na 0 a pokračujeme přes 8 čísel ve směru hodinových ručiček v posloupnosti 1, 2, 3, 0, 1, 2, 3, 0.
Skončíme na 0, takže .
Pro modulus = 2 vytvoříme hodiny s čísly 0, 1.
Začneme na 0 a pokračujeme přes 7 čísel ve směru hodinových ručiček v posloupnosti 1, 0, 1, 0, 1, 0, 1.
Začneme na 0 a pokračujeme přes 7 čísel ve směru hodinových ručiček v posloupnosti 1, 0, 1, 0, 1, 0, 1.
Skončili jsme na 1, takže .
Pro modulus = 3 vytvoříme hodiny s čísly 0, 1, 2.
Začneme na 0 a pokračujeme přes 5 čísel proti směru hodinových ručiček v posloupnosti (5 je záporné) 2, 1, 0, 2, 1.
Začneme na 0 a pokračujeme přes 5 čísel proti směru hodinových ručiček v posloupnosti (5 je záporné) 2, 1, 0, 2, 1.
Skončili jsme na 1, takže .
Závěr
Máme-li a navýšíme o násobek čísla , skončíme na stejném místě, tedy:
pro libovolné celé číslo .
Například:
Poznámky pro čtenáře
„mod“ v programovacích jazycích a kalkulačkách
Mnoho programovacích jazyků a kalkulaček mají operátor mod typicky znázorněný symbolem %. Budeš-li počítat pro záporné číslo, některé jazyky dají záporný výsledek.
Například:
Například:
-5 % 3 = -2.
Kongruence Modulo
Někdy se můžeš setkat s výrazem:
Ten tvrdí, že je kongruentní modulo . To je podobné, jako výrazy používané zde, nicméně ne zcela stejné.
V následujícím článku vysvětlíme co to znamená a jak to souvisí s výrazy výše.
Chceš se zapojit do diskuze?
Zatím žádné příspěvky.