Arytmetyka modularna — zegar

Co się właśnie stało?

Wskazówka przeszła $a$ kroków wokół tarczy o $n$ pozycjach. Za każdym razem, gdy dobije do końca, wraca na start — liczy się tylko to, gdzie ostatecznie stanie. Ta pozycja to reszta z dzielenia.

Definicja — reszta modulo:

Mówimy, że $a \equiv r \pmod{n}$ („a przystaje do r modulo n"), gdy $a$ i $r$ dają tę samą resztę z dzielenia przez $n$. Krótko: różnią się o wielokrotność $n$.

Analogia zegara:

Zegar 12-godzinny liczy modulo 12. Godzina 15:00 to $15 \bmod 12 = 3$, czyli 3:00 po południu — jedno pełne okrążenie tarczy plus 3 godziny. Tak samo $27 \bmod 12 = 3$ (dwa okrążenia i 3).

Po co to w kryptografii?

Szyfr Cezara przesuwa litery modulo 26 (alfabet „zawija się" z Z na A). RSA i wymiana kluczy Diffiego–Hellmana opierają się na potęgowaniu modulo dużej liczby — działania na okręgu reszt są odwracalne tylko dla znającego klucz. Bez arytmetyki modularnej nie ma nowoczesnego szyfrowania.

Po co Ci to na maturze:

Zadania z resztami, podzielnością i cyklicznością (np. „jaki dzień tygodnia za 100 dni", ostatnia cyfra potęgi) rozwiązujesz jednym chwytem: policz $a \bmod n$. Wypisz $n$, policz resztę — reszta rządzi całym cyklem.

Zapamiętaj: $a \bmod n$ to reszta z dzielenia — liczba na okręgu $n$ pozycji, gdzie $0 \le r < n$. To fundament kryptografii.