Přeskočit na obsah

Zbytek po dělení

Z Wikipedie, otevřené encyklopedie
(přesměrováno z Aritmetika modulo 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“:
Závorky zde označují nejbližší celé číslo menší než podíl a:m. Pro tuto variantu platí:
ale nastávají případy, kdy
např. .
Je-li kladné, pak pro všechna .
  • „Symetrická varianta“:
kde označuje směrem k nule zaokrouhlený podíl . Pro tuto variantu platí
,
ale nastávají případy, kdy
, např. .
zde má stejné znaménko jako , pokud není .

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

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]
Na tuto kapitolu je přesměrováno heslo Operace modulo.

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, N2, N3, N4, …, Ni, … poslední jednu, dvě, tři, čtyři, …, respektive čí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 .

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]
Podrobnější informace naleznete v článku Modulární aritmetika.

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.

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.