Główna zawartość

Co to jest arytmetyka modularna?

Wprowadzenie do matematyki modularnej

Kiedy dzielimy dwie liczby całkowite otrzymuje się następujące równanie:

$\frac{A}{B} = Q reszty R$ ‍

A

to dzielna

B

to dzielnik

Q

to iloraz

R

to reszta

Czasami jesteśmy zainteresowani jedynie resztą z dzielenia

A

przez

B

.
Resztę z dzielenia A przez B zapisujemy za pomocą operatora modulo (w skrócie mod).

Korzystając z powyższych

A

B

Q

, i

R

, otrzymamy:

A mod B = R

Możemy to przeczytać jako

A

modulo

B

jest równe

R

. Gdzie

B

jest określane jako moduł.

Na przykład:

$\begin{array}{rcl} \frac{13}{5} & = & 2 reszty 3 \\ 13 mod 5 & = & 3 \end{array}$ ‍

Wizualizacja operacji modulo na tarczy zegara

Spójrzmy, co dzieje się, gdy zwiększamy liczby o 1, dzieląc następnie przez 3.

$\begin{array}{rcl} \frac{0}{3} & = & 0 reszta 0 \\ \frac{1}{3} & = & 0 reszta 1 \\ \frac{2}{3} & = & 0 reszta 2 \\ \frac{3}{3} & = & 1 reszta 0 \\ \frac{4}{3} & = & 1 reszta 1 \\ \frac{5}{3} & = & 1 reszta 2 \\ \frac{6}{3} & = & 2 reszta 0 \end{array}$ ‍

Kolejne reszty zaczynają się od 0 i rosną o 1, do momentu kiedy argument będzie o jeden mniejszy niż dzielnik. Następnie sekwencja powtarza się.

Zauważając te zależności możemy zwizualizować operację modulo za pomocą okręgów.

Piszemy 0 na górze okręgu i dalej, z godnie z kierunkiem wskazówek zegara kolejne liczby całkowite 1, 2... do jednego mniej niż dzielnik.

Na przykład, tarcza zegara, na której 12 zastąpiono zerem, byłaby okręgiem odpowiadającym arytmetyce modulo 12.

Aby obliczyć

A mod B

, należy wykonać następujące kroki:

Zbudować zegar o rozmiarze $B$ ‍, który zaczyna się od $0$ ‍.
Zaczynamy od $0$ ‍ i idziemy zgodnie z kierunkiem wskazówek zegara $A$ ‍ kroków
Rozwiązanie znajduje się tam gdzie skończymy.

(Jeśli liczba

A

jest dodatnia, poruszamy się zgodnie z ruchem wskazówek zegara, jeśli jest ujemna - przeciwnie.)

Przykłady

$8 mod 4 = ?$ ‍

Dla dzielnika równego 4 konstruujemy zegar z liczbami 0, 1, 2, 3.
Zaczynamy od 0 i idziemy w prawo 8 kroków dookoła zegara. Otrzymujemy sekwencję liczb 1, 2, 3, 0, 1, 2, 3, 0.

Skończyliśmy na więc na 0, a zatem

8 mod 4 = 0

$7 mod 2 = ?$ ‍

Dla dzielnika równego 2 konstruujemy zegar z liczbami 0 i 1.
Zaczynamy od 0 i idziemy w prawo 7 kroków dookoła zegara, otrzymując sekwencję liczb 1, 0, 1, 0, 1, 0, 1.

Skończyliśmy na 1 więc

7 mod 2 = 1

$- 5 mod 3 = ?$ ‍

Dla dzielnika równego 3 konstruujemy zegar z liczbami 0, 1, 2
Zaczynamy od 0 i wykonujemy 5 kroków w kierunku przeciwnym (5 jest ujemna) do ruchu wskazówek zegara. Otrzymujemy sekwencję liczb 2, 1, 0, 2, 1.

Skończyliśmy na 1 więc

- 5 mod 3 = 1

Podsumowanie

Jeśli mamy

A mod B

i zwiększymy

A

poprzez wielokrotność $B$ ‍, będziemy w tym samym miejscu, np.

$A mod B = (A + K \cdot B) mod B$ ‍ dla dowolnego całkowitego $K$ ‍.

Na przykład:

$\begin{array}{r} 3 mod 10 = 3 \\ 13 mod 10 = 3 \\ 23 mod 10 = 3 \\ 33 mod 10 = 3 \end{array}$ ‍

Notatki do Czytelnika

Operacja modulo w językach programowania i na kalkulatorach

Wiele języków programowania i kalkulatorów posiada operator modulo, zazwyczaj oznaczany przez symbol %. Jeśli obliczamy resztę z dzielenia dla ujemnej dzielnej niektóre języki programowania zwracają liczbę ujemną.
np.

-5 % 3 = -2.

Zbieżność modulo

Możesz spotkać się z wyrażeniem:

$A \equiv B (mod C)$ ‍

To oznacza, że

A

jest zbieżne do

B

modulo

C

. Jest to podobne do wyrażeń używanych tutaj, ale trochę inne.

W następnym artykule wyjaśnimy jego znaczenie i w jaki sposób jest związane z używanymi przez nas pojęciami.

Chcesz dołączyć do dyskusji?

Zaloguj się

Sortuj według

Na razie brak głosów w dyskusji

Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.

Informatyka

Kurs: Informatyka > Rozdział 2