Zbytek po dělení

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Zbytek po dělení nebo také modulo je početní operace související s operací celočíselného dělení. Například 7 / 3 = 2 se zbytkem 1. Také můžeme říci, že 7 modulo 3 = 1, zkráceně 7 mod 3 = 1. Je-li zbytek po dělení a/n nula, říkáme že a je dělitelné n.

Záporná čísla[editovat | editovat zdroj]

Protože není intuitivně jasné, jak by se měla operace zbytku po dělení chovat u záporných čísel, používají se přinejmenším dvě definice této operace:

  • „Matematická varianta“:
(a\;\bmod\;m)= a - \left \lfloor \frac{a}{m} \right \rfloor \cdot m
Závorky \lfloor \cdot \rfloor zde označují nejbližší celé číslo menší než podíl a:m. Pro tuto variantu platí:
(a + km)\;\bmod\;m = a\;\bmod\;m\quad(k\in\mathbb Z),
ale nastávají případy, kdy
 (-a)\;\bmod\;m \ne-(a\;\bmod\;m), např. (-2)\;\bmod3=1\ne-2=-(2\;\bmod\;3).
Je-li m kladné, pak a\;\bmod\;m\geq0 pro všechna a.
  • „Symetrická varianta“:
(a\;\bmod\;m) = a - m\cdot (a\,\operatorname{div}\,m);
kde a\,\operatorname{div}\,m označuje směrem k nule zaokrouhlený podíl a/m. Pro tuto variantu platí
(-a)\bmod m = -(a\bmod m),
ale nastávají případy, kdy
(a + km)\;\bmod\;m\ne a\;\bmod\;m, např. (1 - 3)\;\bmod\;3=(-2)\;\bmod\;3=-2\ne 1=1\;\bmod\;3.
a\;\bmod\;m zde má stejné znaménko jako a, pokud není a\;\bmod\;m = 0.

V programovacích jazycích je častěji implementována druhá varianta. Pokud je a\geq 0 a současně m>0, dávají obě varianty stejné výsledky.

Použití[editovat | editovat zdroj]

V praktickém životě se modulo někdy používá jako prostředek pro kontrolu úplnosti a správnosti. Například většina rodných čísel osob narozených po roce 1953 je dělitelných číslem 11.[1]

Operace modulo se hojně využívá v programování a návrhu algoritmů, např. při testu sudosti čísla nebo výpočtu dne v týdnu. Také se často používá při generování kontrolních součtů, které bývají součástí komunikačních protokolů.

Je také důležitou součástí algebry, kde se při konstrukci konečných celočíselných algeber využívá modulární aritmetika.

Operace modulo[editovat | editovat zdroj]

Některé kalkulačky mají tlačítko s funkcí mod a mnoho programovacích jazyků má funkci mod nebo přímo operátor mod nebo %. Zápis operace modulo může být

a % n

nebo

a mod n

nebo

mod(a, n)

Modulo a číselné soustavy[editovat | editovat zdroj]

Platí, že v číselné soustavě o radixu N představuje zbytek po dělení číslem N, N², N³, N4, …, Ni, … poslední jednu, dvě, tři, čtyři, …, respektive i číslic z dělence.

Toho se někdy využívá ve výpočetní technice (kde se v drtivé většině případů používá binární soustava). V případech, kdy je třeba zjistit zbytek po dělení dvěma, čtyřmi, osmi, …, 2i, … se místo (na výpočetní výkon náročnější) operace dělení provádí bitový součin (též bitová konjunkce, operace AND), kde druhým operandem je 2^{i}-1.

Příklad[editovat | editovat zdroj]

170 mod 64

Zbytek po dělení je 42. Druhý operand, 64, je 26, lze tedy použít bitový (binární) součin s číslem 26-1. Pokud bychom tedy spočítali 170 and 63, dostaneme:

číslo binárně číslo dekadicky
10101010 170
and 00111111 63
= 00101010 42

Kongruence modulo n[editovat | editovat zdroj]

O celých číslech říkáme, že jsou kongruentní modulo n (pro celé číslo n větší než jedna), pokud jejich rozdíl je násobkem n. Tato relace tvoří ekvivalenci na množině celých čísel. Například:

  • Čísla 13 a 513 jsou kongruentní modulo 100, neboť jejich rozdíl je 500.
  • Čísla 11 a -9 jsou kongruentní modulo 10, protože jejich rozdíl je 20

Aritmetika modulo n[editovat | editovat zdroj]

Pro celé číslo n větší než jedna aritmetikou modulo n rozumíme množinu celých čísel od 0 do n-1 s operacemi sčítání, odčítání, násobení a dělení definovanými tak, aby výsledek operace byl kongruentní modulo n s výsledkem v klasické algebře.

Příklad: V aritmetice modulo 7 je 5×6 = 2. V obvyklém násobení je 5×6 = 30. Jediné číslo z množiny 0 až 6, které je kongruentní s 30, je číslo 2 (protože 30-4×7 = 2). Výsledek operace je vždy takto jednoznačný.

Jiná (ale ekvivalentní) definice aritmetiky modulo n je, že se jedná o rozklad (tedy množina všech tříd ekvivalence) množiny celých čísel podle relace "a je kongruentní s b modulo n".

Aritmetika modulo n s operací sčítání tvoří komutativní grupu, se sčítáním a násobením tvoří okruh. Je-li n prvočíslo, tvoří dokonce těleso.

Reference[editovat | editovat zdroj]

  1. Katalog datových prvků ISVS

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

  • do-skoly.cz - Online kalkulátor pro výpočet zbytku po dělení 2 reálných čísel včetně zkoušky správnosti výsledku.