Wynik
Bez mod
Pełne obroty
NWD(a, n)

    Więcej o arytmetyce modularnej

    Zegar modularny

    Pięć godzin po 9 jest godzina 2, bo 9 + 5 = 14, a 14 to o 2 więcej niż 12. To właśnie arytmetyka modularna: liczenie na zegarze, który po n zaczyna znowu od 0. Wybierz działanie, podaj n, a i b, a kalkulator poda wynik z rozpisanym każdym krokiem, od reszty z dzielenia po wielokrotne podnoszenie do kwadratu i rozszerzony algorytm Euklidesa, a zegar pokaże, jak dochodzi się do wyniku. Wybierz działanie, a potem podaj moduł n oraz liczby a i b; działają liczby całkowite do 30 cyfr, także ujemne, a n może sięgać 10^18. Zegar ma n pozycji z 0 na górze, a wskazówka pokazuje wynik. Dodawanie i odejmowanie są rysowane jako spirala z b kroków, z jednym pierścieniem na każdy pełny obrót; mnożenie jako skoki o a; potęgi jako cięciwy a, a², a³ …, które zamykają się w cykl; odwrotność i dzielenie jako wielokrotności, które trafiają w 1 lub w a. Kroki pokazują to samo obliczenie na liczbach. Do mod 20 wyświetlana jest tabela działania; kliknij komórkę, aby użyć jej liczb. Przykład wstawia klasyczne zadanie.

    Jak to działa

    1. Wybierz działanie: a mod n, dodawanie, odejmowanie, mnożenie, dzielenie, potęgę lub odwrotność a.
    2. Podaj moduł n oraz liczby a i b albo wybierz przykład, taki jak ostatnia cyfra 7^2026 lub krótka wiadomość RSA.
    3. Odczytaj wynik i kroki, prześledź drogę na zegarze, a do mod 20 kliknij komórkę tabeli, aby wypróbować jej liczby.

    Co oznacza a mod n

    a mod n to reszta z dzielenia a przez n: 17 mod 5 = 2, bo 17 = 3 × 5 + 2. Reszta zawsze wynosi od 0 do n − 1, także dla liczb ujemnych: −7 mod 3 = 2, bo −7 = −3 × 3 + 2. Na zegarze oznacza to przejście 7 kroków wstecz od 0. Dwie liczby o tej samej reszcie są przystające, co zapisujemy 17 ≡ 2 (mod 5) – ten zapis wprowadził Carl Friedrich Gauss w 1801 roku. Sumy, różnice i iloczyny można redukować mod n na każdym etapie, dzięki czemu liczby pozostają małe.

    Gdzie stosuje się arytmetykę modularną

    Zegary i kalendarze działają mod 12, mod 24 i mod 7: 100 dni po środzie jest piątek, bo 100 mod 7 = 2. Cyfry kontrolne wykorzystują ją do wykrywania błędów przy wpisywaniu, od numerów ISBN-10 (mod 11) po numery kart płatniczych (mod 10) i numery IBAN (mod 97). Szyfry przesuwają litery mod 26, a szyfr afiniczny do odszyfrowania potrzebuje odwrotności mod 26. RSA, który chroni dużą część internetu, szyfruje wiadomość m jako m^e mod n i odszyfrowuje inną potęgą: przy n = 3233 mamy 65^17 mod 3233 = 2790 oraz 2790^413 mod 3233 = 65.

    Często zadawane pytania

    Jak obliczyć a mod n dla liczby ujemnej?

    Dodawaj lub odejmuj wielokrotności n, aż liczba znajdzie się między 0 a n − 1. Dla −7 mod 3: −7 + 9 = 2, więc wynik to 2. Niektóre języki programowania zwracają zamiast tego −1 dla −7 % 3, bo zaokrąglają iloraz w stronę zera; w matematyce reszta nigdy nie jest ujemna.

    Czym jest odwrotność modularna?

    Odwrotność a mod n to liczba x, dla której a × x ≡ 1 (mod n). Odwrotnością 7 mod 26 jest 15, bo 7 × 15 = 105 = 4 × 26 + 1. Istnieje ona tylko wtedy, gdy a i n nie mają wspólnego czynnika, a znajduje ją rozszerzony algorytm Euklidesa. Dzielenie przez a mod n oznacza mnożenie przez odwrotność a.

    Jak obliczyć mod n potęgę taką jak 7^2026?

    Przez wielokrotne podnoszenie do kwadratu: podnoś 7 do kwadratu raz za razem, za każdym razem redukując mod n, aby otrzymać 7^1, 7^2, 7^4, 7^8 i tak dalej, a potem pomnóż te potęgi, które składają się na 2026 w zapisie dwójkowym. Wymaga to 10 podniesień do kwadratu i 7 mnożeń zamiast 2 025 mnożeń, a liczby nigdy nie przekraczają n². 7^2026 kończy się cyfrą 9.

    Dlaczego zegar pokazuje 0 zamiast 12?

    W arytmetyce modularnej reszty biegną od 0 do n − 1, więc na zegarze z 12 pozycjami południe to 0. 12 ≡ 0 (mod 12); zwykły zegar po prostu pokazuje 12 tam, gdzie matematyka pisze 0.

    Jak duże mogą być liczby?

    a i b mogą mieć do 30 cyfr i mogą być ujemne, a moduł może sięgać 10^18. Kalkulator działa na dokładnych liczbach całkowitych w twojej przeglądarce, więc nawet przykłady wielkości RSA dają dokładne wyniki, a nic nie jest nigdzie wysyłane.

    Chcesz wypróbować?

    Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

    Przejdź do edytora