Hlavní obsah

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:

$\frac{A}{B} = Q a zbytek R$ ‍

A

je dělenec

B

je dělitel

Q

je podíl

R

je zbytek

Někdy nás zajímá jen jaký je zbytek po dělení čísla

A

číslem

B

.
Pro tyto případy je operátor zvaný modulo (zkráceně „mod“).

Použitím stejných

A

B

Q

R

jako výše, dostaneme:

A mod B = R

Čteme jako

A

modulo

B

je rovno

R

, kde je

B

je někdy označováno jako modulus.

Například:

$\begin{array}{rcl} \frac{13}{5} & = & 2 zbytek 3 \\ 13 mod 5 & = & 3 \end{array}$ ‍

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.

$\begin{array}{rcl} \frac{0}{3} & = & 0 zbytek 0 \\ \frac{1}{3} & = & 0 zbytek 1 \\ \frac{2}{3} & = & 0 zbytek 2 \\ \frac{3}{3} & = & 1 zbytek 0 \\ \frac{4}{3} & = & 1 zbytek 1 \\ \frac{5}{3} & = & 1 zbytek 2 \\ \frac{6}{3} & = & 2 zbytek 0 \end{array}$ ‍

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

A mod B

držme se těchto kroků:

Sestavme hodiny pro velikost $B$ ‍
Začněme na 0 a a pokračujme dále po $A$ ‍ 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

$8 mod 4 = ?$ ‍

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.

Skončíme na 0, takže

8 mod 4 = 0

$7 mod 2 = ?$ ‍

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.

Skončili jsme na 1, takže

7 mod 2 = 1

$- 5 mod 3 = ?$ ‍

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.

Skončili jsme na 1, takže

- 5 mod 3 = 1

Závěr

Máme-li

A mod B

a navýšíme

A

o násobek čísla $B$ ‍, skončíme na stejném místě, tedy:

$A mod B = (A + K \cdot B) mod B$ ‍ pro libovolné celé číslo $K$ ‍.

Například:

$\begin{array}{r} 3 mod 10 = 3 \\ 13 mod 10 = 3 \\ 23 mod 10 = 3 \\ 33 mod 10 = 3 \end{array}$ ‍

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:

-5 % 3 = -2.

Kongruence Modulo

Někdy se můžeš setkat s výrazem:

$A \equiv B (mod C)$ ‍

Ten tvrdí, že

A

je kongruentní

B

modulo

C

. 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?

Přihlášení

Setřídit podle:

Zatím žádné příspěvky.

Umíš anglicky? Kliknutím zobrazíš diskuzi anglické verze Khan Academy.

Informatika

Kurz: Informatika > Kapitola 1

Co je to modulární aritmetika?

Úvod do modulární aritmetiky

Znázornění operace modulo pomocí hodin.

Příklady

$8 mod 4 = ?$ ‍

$7 mod 2 = ?$ ‍

$- 5 mod 3 = ?$ ‍

Závěr

Poznámky pro čtenáře

„mod“ v programovacích jazycích a kalkulačkách

Kongruence Modulo

Chceš se zapojit do diskuze?

Informatika

Kurz: Informatika > Kapitola 1

Úvod do modulární aritmetiky

Znázornění operace modulo pomocí hodin.

Příklady

8 mod 4=?‍

7 mod 2=?‍

−5 mod 3=?‍

Závěr

Poznámky pro čtenáře

„mod“ v programovacích jazycích a kalkulačkách

Kongruence Modulo

Chceš se zapojit do diskuze?

$8 mod 4 = ?$ ‍

$7 mod 2 = ?$ ‍

$- 5 mod 3 = ?$ ‍