Po co jest modulo i arytmetyka modularna?
W kalkulatorze arytmetyki modularnej policzysz resztę z dzielenia (a mod n), działania modulo oraz szybkie potęgowanie modularne. Takie obliczenia pojawiają się w zadaniach z kongruencji, w kryptografii (np. RSA) i w programowaniu.
Jeśli liczysz też logikę, zobacz tablicę prawdy. Gdy zadanie przechodzi do zbiorów, przyda się kalkulator działań na zbiorach, a do własności grafów stopnie wierzchołków grafu oraz graf pełny.
Wzór i logika obliczeń
Resztę z dzielenia zapisujemy jako a mod n. W praktyce wygodnie sprowadzić wynik do zakresu 0…n−1 (tzw. reszta nieujemna).
Najczęstsze działania:
- (a + b) mod n – dodawanie modulo
- (a − b) mod n – odejmowanie modulo
- (a · b) mod n – mnożenie modulo
- a^b mod n – potęgowanie modularne (liczone szybko metodą „square & multiply”)
Odwrotność a^(-1) mod n istnieje tylko wtedy, gdy NWD(a,n)=1. Kalkulator pokaże NWD i (jeśli się da) obliczy odwrotność metodą rozszerzonego Euklidesa.
Przykład obliczeń
Przykład 1: 29 mod 7 = 1, bo 29 = 4·7 + 1. Jeśli a jest ujemne, np. −3 mod 7 = 4 (sprowadzamy do 0…6).
Przykład 2: 7^128 mod 13 liczymy szybkim potęgowaniem – kalkulator zrobi to bezpośrednio, nawet dla dużych wykładników.
Zadanie przykładowe i rozwiązanie (1)
Zadanie: Oblicz −35 mod 12.
Rozwiązanie: Wpisz a = −35, n = 12 i wybierz tryb a mod n. Kalkulator poda wynik z zakresu 0…11 (czyli resztę nieujemną).
To częste pytanie: „jak policzyć ujemne modulo”.
Zadanie przykładowe i rozwiązanie (2)
Zadanie: Policz 3^200 mod 17 (typowe w kryptografii).
Rozwiązanie: Wybierz tryb a^b mod n, wpisz a=3, b=200, n=17. Kalkulator użyje szybkiego potęgowania modularnego.
Takie zapytanie często pada jako „potęgowanie modularne kalkulator”.
Zadania do samodzielnego rozwiązania
Policz najpierw samodzielnie, a potem sprawdź wynik w kalkulatorze. Te przykłady są dobre do powtórki przed kartkówką z kongruencji, reszt z dzielenia i potęgowania modularnego.
Oblicz 47 mod 9 i zapisz, w jakim zakresie powinien znaleźć się wynik.
Oblicz −18 mod 7. Pamiętaj o sprowadzeniu reszty do zakresu 0…6.
Oblicz 5^13 mod 11 i sprawdź wynik trybem potęgowania modularnego.
Sprawdź, czy istnieje odwrotność modularna 8^(-1) mod 21. Najpierw policz NWD(8,21).
Odpowiedzi do sprawdzenia
1) 47 mod 9 = 2. 2) −18 mod 7 = 3. 3) 5^13 mod 11 = 5. 4) NWD(8,21)=1, więc odwrotność istnieje; 8^(-1) mod 21 = 8, bo 8·8=64, a 64 mod 21 = 1.
Tabela: skrót najczęstszych operacji
| Operacja | Zapis | Po co? | Uwaga |
|---|---|---|---|
| Modulo | a mod n | reszta z dzielenia | n > 0 |
| Dodawanie | (a+b) mod n | szybkie sumy w kongruencjach | redukuj do 0…n−1 |
| Mnożenie | (a·b) mod n | RSA, algorytmy | BigInt przy dużych liczbach |
| Potęgowanie | a^b mod n | kryptografia | szybkie „square & multiply” |
| Odwrotność | a^(-1) mod n | dzielenie modulo | tylko gdy NWD(a,n)=1 |
Do zadań z liczbami pierwszymi sprawdź liczby pierwsze i rozkład, a do kombinatoryki wariacje i kombinacje.
Tabela porównawcza: modulo w matematyce i w programowaniu
| Temat | Matematyka | Programowanie | W kalkulatorze |
|---|---|---|---|
| Ujemne a | wynik w 0…n−1 | bywa ujemny | zawsze 0…n−1 |
| Duże liczby | dokładnie | przepełnienia typów | BigInt |
| Odwrotność | istnieje gdy NWD=1 | dzielenie modulo | pokazuje warunek i wynik |
W zadaniach „na RSA” najczęściej pojawia się potęgowanie modularne i odwrotność modularna. Do logiki w dyskretnej – tablica prawdy.
Ciekawostka
W RSA szyfrowanie i odszyfrowanie to potęgowanie modularne na bardzo dużych liczbach: c = m^e mod n oraz m = c^d mod n.
Najczęstsze błędy i jak zwiększyć dokładność wyniku
- n = 0 – modulo przez 0 nie ma sensu. Ustaw n ≥ 1.
- Ujemne modulo – w matematyce najczęściej używa się reszty nieujemnej 0…n−1.
- Odwrotność bez warunku – jeśli NWD(a,n) ≠ 1, to odwrotność nie istnieje.
- Potęgowanie „na piechotę” – dla dużego b używaj szybkiego potęgowania modularnego.
Jeśli wpisujesz „jak policzyć a^b mod n”, wybierz tryb potęgowania modularnego – to najszybsza metoda.
Powiązane kalkulatory matematyki dyskretnej
Modulo jest jednym z podstawowych narzędzi matematyki dyskretnej, dlatego najlepiej działa razem z logiką, zbiorami, NWD i grafami. Jeśli uczeń wpisuje w Google „arytmetyka modularna kalkulator”, często chwilę później potrzebuje też tablic prawdy, działań na zbiorach albo grafów.
Dwa praktyczne zastosowania
Modulo pozwala zamieniać „duże” rachunki na małe reszty. To skraca zadania typu „jaka jest reszta z dzielenia…”.
Szyfrowanie to potęgowanie modularne, a odwrotność modularna pojawia się przy wyznaczaniu wykładnika prywatnego.
Do kombinatoryki w dyskretnej zajrzyj do wariacji i kombinacji, a do logiki do tablicy prawdy.
Wskazówka od KalkulatorXXL
Jeśli masz ujemne a, sprowadź wynik do 0…n−1: policz resztę i w razie potrzeby dodaj n. Ten kalkulator robi to automatycznie.
Cały dział matematyki dyskretnej: Akademia matematyki dyskretnej – logika, zbiory i grafy łączy tablice prawdy, prawa De Morgana, zbiory, relacje, modulo, kongruencje, podzielność, kombinatorykę, prawdopodobieństwo i teorię grafów.
Cały pakiet: matematyka dyskretna, logika, zbiory i grafy
Ten kalkulator należy do jednego pakietu z zakresu matematyki dyskretnej. Jeżeli pracujesz z logiką i zbiorami, przejdź kolejno przez tablica prawdy, prawa De Morgana, działania na zbiorach oraz relacje i własności relacji. Te narzędzia pomagają rozumieć zapisy zdań, negacje, diagramy Venna i własności relacji.
Jeśli zadanie dotyczy reszt z dzielenia, wybierz modulo i reszty z dzielenia, kongruencje liniowe albo rozszerzony algorytm Euklidesa. Do zadań z gwarantowanym powtórzeniem pasuje zasada szufladkowa Dirichleta, szczególnie gdy szufladami są reszty modulo, kolory, miesiące lub inne klasy.
Część grafową tworzą: stopnie wierzchołków grafu, graf pełny Kₙ, drzewa w grafach, ścieżki i cykle w grafie i macierz sąsiedztwa grafu. Dzięki temu możesz przejść od listy krawędzi, przez macierz sąsiedztwa, aż po stopnie, cykle, drzewa i graf pełny.