Arytmetyka modularna — matematyka zegara, mod i kongruencja

Arytmetyka modularna polega na pracy z resztami z dzielenia przez ustaloną dodatnią liczbę całkowitą, zwaną modułem. Jeśli dwie liczby dają tę samą resztę, zachowują się tak samo w tym układzie modularnym, dlatego mówi się o niej także matematyka zegara.

Na zegarze $12$-godzinnym godzina $13$ wypada na $1$, a $29$ godzin trafia w to samo miejsce co $5$ godzin. Ten powtarzający się cykl daje intuicję stojącą za arytmetyką modularną.

Co oznacza mod w arytmetyce modularnej

Dla liczby całkowitej $a$ i dodatniej liczby całkowitej $n$, wyrażenie $a \bmod n$ oznacza resztę z dzielenia $a$ przez $n$.

Przykład:

$$29 \bmod 12 = 5$$

ponieważ

$$29 = 12 \cdot 2 + 5$$

Moduł wynosi $12$, więc dodanie lub odjęcie $12$ nie zmienia miejsca, w którym lądujemy w cyklu.

Co oznacza kongruencja modulo $n$

Kongruencja to formalny sposób powiedzenia, że dwie liczby całkowite zachowują się tak samo modulo $n$.

$$a \equiv b \pmod n$$

oznacza, że $a$ i $b$ dają tę samą resztę przy dzieleniu przez $n$. Równoważnym testem jest

$$n \mid (a-b)$$

co oznacza „$n$ dzieli $a-b$”.

Zatem

$$29 \equiv 5 \pmod{12}$$

ponieważ $29 - 5 = 24$, a $12$ dzieli $24$.

To rozróżnienie jest ważne:

• $29 \bmod 12 = 5$ to stwierdzenie o reszcie.
• $29 \equiv 5 \pmod{12}$ to stwierdzenie o kongruencji.

Są ze sobą powiązane, ale nie są zamienne.

Przykład: $29$ godzin po godzinie $8$

Załóżmy, że teraz jest godzina $8$ i chcesz wiedzieć, która będzie godzina za $29$ godzin na zegarze $12$-godzinnym.

Najpierw zredukuj $29$ modulo $12$:

$$29 \bmod 12 = 5$$

Zatem dodanie $29$ godzin daje ten sam efekt co dodanie $5$ godzin:

$$8 + 29 \equiv 8 + 5 \pmod{12}$$

Wtedy

$$8 + 29 \equiv 13 \equiv 1 \pmod{12}$$

Zegar pokaże więc godzinę $1$.

Kluczowym ruchem jest krok redukcji. Modulo $12$ zastąpienie $29$ przez $5$ nie zmienia odpowiedzi, a upraszcza rachunki.

Dlaczego wcześniejsza redukcja ułatwia zadania

Duże liczby często łatwiej obliczać po zastąpieniu ich mniejszą liczbą kongruentną.

Na przykład modulo $7$,

$$100 \equiv 2 \pmod 7$$

ponieważ $100 - 2 = 98$ jest podzielne przez $7$. Jeśli zadanie dotyczy tylko wartości modulo $7$, możesz pracować z $2$ zamiast z $100$.

Typowe błędy

Mylenie równości z kongruencją

$29 \equiv 5 \pmod{12}$ nie oznacza, że $29 = 5$. Oznacza to, że należą do tej samej klasy reszt modulo $12$.

Zapominanie, że moduł ma znaczenie

$17 \equiv 5 \pmod{12}$ jest prawdą, ale $17 \equiv 5 \pmod{10}$ jest fałszem. Kongruencja zawsze odnosi się do konkretnego modułu.

Traktowanie mod jak zwykłego dzielenia

$29 \bmod 12$ to reszta $5$, a nie iloraz $2$ i nie ułamek $29/12$.

Zakładanie, że operator % w programach zawsze odpowiada tej samej konwencji matematycznej

Dla liczb dodatnich operator % w językach programowania często odpowiada pojęciu reszty, którego uczniowie uczą się najpierw. Dla liczb ujemnych konwencje mogą się różnić, więc wynik może nie zgadzać się z najmniejszą nieujemną resztą używaną na wielu kursach matematyki.

Gdzie używa się arytmetyki modularnej

Arytmetyka modularna pojawia się wszędzie tam, gdzie wartości powtarzają się cyklicznie: na zegarach, w dniach tygodnia, systemach cyfr kontrolnych, haszowaniu i w wielu działach teorii liczb.

Występuje też w kryptografii, ale nadal obowiązuje ta sama podstawowa idea: liczby grupuje się według ich reszt, a liczby kongruentne można traktować jako równoważne w obrębie tego układu.

Spróbuj podobnego zadania

Jaki dzień tygodnia będzie $100$ dni po poniedziałku? Ponieważ dni powtarzają się modulo $7$, zacznij od zredukowania $100$ modulo $7$, zanim odpowiesz.

Jeśli chcesz porównać jeszcze jeden przypadek, wypróbuj własną wersję w GPAI Solver i zobacz, czy wcześniejsza redukcja skraca obliczenia.