Wprowadzenie do matematyki modularnej

Kiedy dzielimy dwie liczby całkowite otrzymuje się następujące równanie:
AB=Q reszty R \dfrac{A}{B} = Q \text{ reszty } R
A A to dzielna
B B to dzielnik
Q Q to iloraz
R R to reszta
Czasami jesteśmy zainteresowani jedynie resztą z dzielenia A A przez B B .
  Resztę z dzielenia A przez B zapisujemy za pomocą operatora modulo (w skrócie mod).
Korzystając z powyższych A A , B B , Q Q , i R R , otrzymamy: A mod B=R A \text{ mod } B = R
Możemy to przeczytać jako A A modulo B B jest równe R R . Gdzie B B jest określane jako moduł.
Na przykład:

Wizualizacja operacji modulo na tarczy zegara

Spójrzmy, co dzieje się, gdy zwiększamy liczby o 1, dzieląc następnie przez 3.
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 znaleźć wynik  mod B \text{ mod } B możemy podążać następującymi krokami:
  1. Zbudować zegar o rozmiarze B B , który zaczyna się od 00.
  2. Zaczynamy od 00 i idziemy zgodnie z kierunkiem wskazówek zegara A A
  3. Rozwiązanie znajduje się tam gdzie skończymy.
(Jeśli liczba jest dodatnia, poruszamy się zgodnie z ruchem wskazówek zegara, jeśli jest ujemna - przeciwnie.)

Przykłady

8 mod 4=? 8 \text{ 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 8 \text{ mod } 4 = \bf{0} .

7 mod 2=? 7 \text{ 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 7 \text{ mod } 2 = \bf{1} .

5 mod 3=? -5 \text{ 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 -5 \text{ mod } 3 = \bf{1} .

Podsumowanie

Jeśli mamy A mod B A \text{ mod } B i zwiększymy A A poprzez wielokrotność B \bf{B} , będziemy w tym samym miejscu, np.
A mod B=(A+KB) mod B A \text{ mod } B = (A + K \cdot B) \text{ mod } B  dla dowolnego całkowitego K \bf{K} .
Na przykład:

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:
AB (mod C) A \equiv B\ (\text{mod } C)
To oznacza, że A A jest zbieżne do B B modulo C 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.
Ładowanie