Zbytek po dělení

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

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\neq -(a\;{\bmod {\;}}m),$ např. $(-2)\;{\bmod {3}}=1\neq -2=-(2\;{\bmod {\;}}3)$.

Je-li $m$ kladné, pak $a\;{\bmod {\;}}m\geq 0$ 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\neq a\;{\bmod {\;}}m$, např. $(1-3)\;{\bmod {\;}}3=(-2)\;{\bmod {\;}}3=-2\neq 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í

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.

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

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

Platí, že v číselné soustavě o radixu N představuje zbytek po dělení číslem N, N², N³, N⁴, …, Nⁱ, … 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, …, 2ⁱ, … 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

170 mod 64

Zbytek po dělení je 42. Druhý operand, 64, je 2⁶, lze tedy použít bitový (binární) součin s číslem 2⁶-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

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

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

• Euklidův algoritmus

Externí odkazy

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