V matematice je výsledkem operace modulo zbytek aritmetického dělení. Jak je známo, aritmetické dělení dvou celých čísel dává kvocient a zbytek.

Jsou však možné i jiné konvence. Počítače a kalkulačky mají různé způsoby ukládání a reprezentace čísel. Jejich definice operace modulo závisí na programovacím jazyce a/nebo základním hardwaru.

Definice a notace

Operaci modulo obvykle zapisujeme jako a mod n nebo pomocí symbolu % v programovacích jazycích. Matematicky: pro celá čísla a a n (s n ≠ 0) existují celá čísla q a r taková, že

a = q·n + r, kde r je zbytek. Různé definice se liší právě vlastností r; běžná matematická (Euclidova) konvence požaduje 0 ≤ r < |n|.

Pro kladné dělitele n lze r vyjádřit formálně jako

r = a − n·floor(a / n), což dává r v intervalu [0, n) pro n > 0.

Vlastnosti a základní vztahy

  • Rozsah zbytku: podle konvence může být r buď v intervalu [0, |n|) (Euclidova definice), nebo mít stejný znaménkový směr jako dělitel či dělenec (záleží na implementaci).
  • Kompatibilita s kongruencí: a ≡ b (mod n) znamená, že n dělí rozdíl a−b. Modulo tedy rozděluje celá čísla do tříd zbytků.
  • Operace sčítání a násobení: (a + b) mod n = ((a mod n) + (b mod n)) mod n a (a·b) mod n = ((a mod n)·(b mod n)) mod n.
  • Modulo nulou: dělení nulou není definované, takže a mod 0 je nedefinované.
  • Inverzní prvek: prvek a má multiplikativní inverzi modulo n právě tehdy, když gcd(a,n) = 1.

Konvence v programování a rozdíly mezi jazyky

V praxi mají jazyky různé konvence pro znaménko zbytku:

  • Trunkovaná dělitelnost (remainder) — kvocient se zaokrouhluje směrem k nule; zbytek má stejné znaménko jako dělenec (dividend). Takové chování mají například jazyky C/C++ (standard C99 a novější), Java a JavaScript. Příklad: v těchto jazycích -5 % 3 == -2.
  • Floored division (Euclidovská verze) — kvocient se zaokrouhluje dolů (floor); zbytek má stejné znaménko jako dělitel (divisor) a je nenegativní, pokud je dělitel kladný. Python, Ruby a některé funkce v matematických knihovnách používají tuto konvenci. Příklad: v Pythonu -5 % 3 == 1 (protože -5 = (-2)·3 + 1).
  • Jiné názvy a varianty: v některých jazycích nebo knihovnách najdete dvě funkce — např. v Haskellu rem (remainder) a mod (euclidean mod), které se liší znaménkem výsledku.

Důležitá poznámka: při přenosu algoritmů mezi jazyky dejte pozor na tyto rozdíly — chování modulo s negativními čísly může ovlivnit indexování polí, cyklické posuny nebo kryptografické výpočty.

Příklady

  • Matematika (Euclid): 17 mod 5 = 2, protože 17 = 3·5 + 2 a 0 ≤ 2 < 5.
  • Negativní příklad — rozdílné konvence:
    • Podle trunkované konvence: -5 / 3 → q = -1, r = -5 − (−1)·3 = −2 → -5 % 3 = −2.
    • Podle floored konvence: floor(-5/3) = -2, r = -5 − (−2)·3 = 1 → -5 mod 3 = 1.
  • Využití v praxi: (a + b) mod n často použito pro rotace indexů v kruhových bufferech; modular exponentiation (a^e mod n) je klíčová v kryptografii (např. RSA).

Implementace a výpočty

Z technického hlediska lze zbytek získat buď klasickým celočíselným dělením (kvocient a zbytek) nebo opakovaným odčítáním dělitele. Pro velká čísla se používají efektivní algoritmy (např. Barrett nebo Montgomery redukce) zejména v kryptografii.

Závěr

Operace modulo je jednoduchý, avšak velmi užitečný koncept jak v matematice, tak v programování. Při práci s ní je však klíčové vědět, jaká konvence je v daném jazyce nebo knihovně použita — zejména pro záporné hodnoty nebo při přenosu kódu mezi prostředími. Modulovací operace není definována pro dělitele 0 a pro matematické důsledky (např. inverze modulo n) je rozhodující nejčastěji vztah s gcd(a,n).