Jeśli jest wtorek, to za 7 dni znów będzie wtorek, za 14 dni też. Żeby wiedzieć, jaki będzie dzień za 100 dni, nie liczymy po kolei: wystarczy wiedzieć, ile dni zostaje po wyrzuceniu pełnych tygodni. To właśnie robi działanie modulo.
Co znaczy a mod n
Zapis a mod n oznacza resztę z dzielenia liczby a przez n. Skoro 100 = 7 · 14 + 2, to 100 mod 7 = 2. Reszta jest zawsze liczbą od 0 do n − 1, więc przy dzieleniu przez 7 możliwe reszty to 0, 1, 2, 3, 4, 5 i 6. Liczby, które dają tę samą resztę, są w pewnym sensie „takie same” przy tym dzieleniu: 2, 9, 16 i 100 mają resztę 2 przy dzieleniu przez 7.
| Zapis | Rachunek | Wynik |
|---|---|---|
| 87 mod 5 | 87 = 5 · 17 + 2 | 2 |
| 150 mod 7 | 150 = 7 · 21 + 3 | 3 |
| 48 mod 8 | 48 = 8 · 6 + 0 | 0 |
| 3 mod 10 | 3 = 10 · 0 + 3 | 3 |
Dni tygodnia i godziny
Dni tygodnia „zapętlają się” co 7, godziny na zegarze 24-godzinnym co 24, a minuty co 60. W każdej takiej sytuacji liczymy modulo długość cyklu.
Podobnie z godzinami: jest 20:00, a za 100 godzin? 20 + 100 = 120, a 120 mod 24 = 0, więc będzie godzina 0:00, czyli północ. Cztery pełne doby i jeszcze dokładnie 24 godziny przesuwają nas z powrotem na tę samą godzinę.
Liczenie na samych resztach
Wielkie liczby można zastępować ich resztami. Obowiązują dwie reguły:
- Suma: (a + b) mod n = ((a mod n) + (b mod n)) mod n.
- Iloczyn: (a · b) mod n = ((a mod n) · (b mod n)) mod n.
Przykład: (123 · 456) mod 5. Mamy 123 mod 5 = 3 i 456 mod 5 = 1, więc iloczyn reszt to 3 · 1 = 3. Szukana reszta to 3. Sprawdzenie: 123 · 456 = 56 088, a 56 088 = 5 · 11 217 + 3. Zgadza się, a rachunek był o wiele krótszy.
Ostatnia cyfra wielkiej potęgi
Ostatnia cyfra liczby to jej reszta modulo 10. Ostatnie cyfry kolejnych potęg powtarzają się cyklicznie. Dla liczby 7 są to: 7, 9, 3, 1, potem znów 7, 9, 3, 1 i tak dalej, co 4 potęgi. Chcemy ostatnią cyfrę liczby 7⁴⁰. Wykładnik 40 dzieli się przez 4 bez reszty, więc trafiamy na ostatni wyraz cyklu, czyli 1. Dla 7³⁸ mamy 38 mod 4 = 2, więc druga cyfra cyklu, czyli 9.
| Podstawa | Cykl ostatnich cyfr | Długość |
|---|---|---|
| 2 | 2, 4, 8, 6 | 4 |
| 3 | 3, 9, 7, 1 | 4 |
| 4 | 4, 6 | 2 |
| 7 | 7, 9, 3, 1 | 4 |
| 8 | 8, 4, 2, 6 | 4 |
| 9 | 9, 1 | 2 |
Gdzie spotkasz modulo
- Cyfra kontrolna: w numerze PESEL i w kodach kreskowych ostatnia cyfra jest liczona właśnie modulo, żeby wykryć pomyłkę przy przepisywaniu.
- Szyfrowanie: szyfr Cezara przesuwa litery o stałą liczbę miejsc, modulo długość alfabetu (32 w polskim).
- Programowanie: operator % zwraca resztę, a używa się go do sprawdzania parzystości (n % 2) i zapętlania indeksów.
Najczęstsze błędy
- Podanie wyniku dzielenia zamiast reszty: 100 mod 7 to 2, a nie 14.
- Zapominanie, że reszta jest mniejsza od dzielnika. Wynik 7 mod 7 to 0, a nie 7.
- Pomijanie ostatniego wyrazu cyklu przy potęgach: gdy wykładnik dzieli się przez długość cyklu, bierzemy ostatnią cyfrę cyklu, a nie pierwszą.
- Dodawanie reszt bez ponownego zredukowania: 4 + 5 = 9 przy modulo 7 to nie 9, tylko 2.
Sprawdź siebie
1. Oblicz 250 mod 9.
Pokaż rozwiązanie
2. Dziś jest piątek. Jaki dzień będzie za 50 dni?
Pokaż rozwiązanie
3. Oblicz (347 · 212) mod 6.
Pokaż rozwiązanie
4. Jaka jest ostatnia cyfra liczby 3²⁵?
Pokaż rozwiązanie
Zapamiętaj
- a mod n to reszta z dzielenia a przez n, zawsze od 0 do n − 1.
- Sumy i iloczyny można liczyć na resztach, byle na końcu znów wziąć resztę.
- Ostatnie cyfry potęg się powtarzają, więc wystarczy znać cykl.
Poćwicz w grze Reszta z dzielenia (modulo).
Komentarze