Kalkulator chińskiego twierdzenia o resztach
Rozwiązuje układ kongruencji przy użyciu chińskiego twierdzenia o resztach. Wprowadź reszty i parami względnie pierwsze moduły, aby otrzymać najmniejsze nieujemne rozwiązanie.
Rozwiązywanie układów kongruencji
Wzór chińskiego twierdzenia o resztach
Gdzie:
- \(a_i\) — reszty (wartości, którym \(x\) ma być kongruentne)
- \(n_i\) — moduły, które muszą być parami względnie pierwsze (największy wspólny dzielnik każdej pary z nich równa się 1)
- \(N\) — iloczyn wszystkich modułów, który przy zachowaniu względnej pierwszości jest równy ich najmniejszej wspólnej wielokrotności
- \(N_i\) — iloczyn wszystkich modułów z wyjątkiem \(n_i\)
- \(y_i\) — odwrotność \(N_i\) modulo \(n_i\), czyli liczba spełniająca \(N_i y_i \equiv 1 \pmod{n_i}\)
- \(x\) — jedyne rozwiązanie modulo \(N\)
Twierdzenie mówi, że gdy moduły są parami względnie pierwsze, układ ma dokładnie jedno rozwiązanie w zakresie \(0 \le x < N\). Wzór buduje to rozwiązanie, łącząc każdą resztę z odwrotnością odpowiedniego iloczynu częściowego.
Chińskie twierdzenie o resztach — przykład obliczenia
Przykład: znajdź \(x\) takie, że \(x \equiv 2 \pmod{3}\) oraz \(x \equiv 3 \pmod{5}\) — są to domyślne wartości kalkulatora.
\[ N = 3 \times 5 = 15 \]
\[ N_1 = \frac{15}{3} = 5, \quad y_1 = 2 \; (\text{ponieważ } 5 \cdot 2 = 10 \equiv 1 \pmod{3}) \]
\[ N_2 = \frac{15}{5} = 3, \quad y_2 = 2 \; (\text{ponieważ } 3 \cdot 2 = 6 \equiv 1 \pmod{5}) \]
\[ x \equiv (2 \cdot 5 \cdot 2) + (3 \cdot 3 \cdot 2) \pmod{15} \equiv 20 + 18 = 38 \equiv 8 \pmod{15} \]
Wynik: \(x = 8\) modulo \(15\). Rzeczywiście, \(8 \div 3 = 2\) z resztą \(2\) oraz \(8 \div 5 = 1\) z resztą \(3\), więc obie kongruencje są spełnione. Kolejne rozwiązanie to \(8 + 15 = 23\), potem \(38\) itd.
Jak korzystać z kalkulatora
- Wprowadź Liczba kongruencji (co najmniej 2). Kolejne pary reszta/moduł pojawią się automatycznie.
- Dla pierwszej kongruencji wpisz resztę w pole reszta 1 (\(a_1\)) i moduł w pole moduł 1 (\(n_1\)).
- Powtórz dla reszty 2 / modułu 2 oraz ewentualnych kolejnych par.
- Odczytaj Najmniejsze nieujemne rozwiązanie \(x\) oraz Modulo (NWW modułów) \(N\). Każda liczba postaci \(x + kN\) (\(k = 0, 1, 2, \dots\)) również spełnia układ.
Czym jest chińskie twierdzenie o resztach?
Chińskie twierdzenie o resztach (CRT, z ang. Chinese Remainder Theorem) to klasyczny wynik teorii liczb, po raz pierwszy opisany przez chińskiego matematyka Sunzi około III–V w. n.e. Odpowiada ono na pytanie: mając kilka dzielników oraz reszty pozostałe po dzieleniu nieznanej liczby przez każdy z nich, czy można tę liczbę odtworzyć? Twierdzenie mówi, że tak — pod warunkiem, że moduły są parami względnie pierwsze — i że odpowiedź jest jednoznaczna w zakresie o długości równej iloczynowi wszystkich modułów.
Ilustruje to przykład: jeśli koszyk zawiera \(x\) jajek, liczenie ich po 3 zostawia resztę 2, a liczenie po 5 — resztę 3, to \(x \equiv 2 \pmod{3}\) oraz \(x \equiv 3 \pmod{5}\). Twierdzenie jednoznacznie wyznacza \(x\) modulo 15 — w tym przypadku \(x = 8, 23,! 38, \dots\)
Twierdzenie jest ważne, ponieważ pokazuje, że układ wielu małych kongruencji jest równoważny jednej kongruencji o dużym module. Dzięki temu arytmetykę z ogromnym modułem można zastąpić równoległą arytmetyką na kilku małych, wygodnych modułach, a następnie połączyć wyniki. Krok łączenia wykorzystuje odwrotności modulo, które można obliczyć osobno kalkulatorem odwrotności modulo; odwrotności tego rodzaju łączą się także z małym twierdzeniem Fermata i twierdzeniem Eulera.
Interpretacja wyniku
Kalkulator zwraca najmniejsze nieujemne rozwiązanie \(x\) oraz łączny moduł \(N\). Pełny zbiór rozwiązań to \(x, x + N, x + 2N, \dots\), a jeśli w twoim zadaniu sensowne są odpowiedzi ujemne, \(x - N\) i mniejsze wartości również są poprawne. Ponieważ rozwiązanie jest jednoznaczne modulo \(N\), dwa różne zestawy danych dające tę samą wartość \(x \pmod{N}\) opisują dokładnie ten sam układ.
Założenia i ograniczenia
- Moduły muszą być parami względnie pierwsze. Każda para modułów nie może mieć wspólnego dzielnika większego niż 1; w przeciwnym razie kalkulator zgłosi błąd. Jeśli dwa moduły to np. 4 i 6 (oba podzielne przez 2), układ może w ogóle nie mieć rozwiązania albo mieć kilka rozwiązań modulo ich NWW.
- Zgodność układu. Przy modułach względnie pierwszych twierdzenie zawsze daje rozwiązanie — to jest właśnie siła CRT. Sprzeczności między kongruencjami mogą powstać wyłącznie wtedy, gdy warunek względnej pierwszości jest naruszony.
- Reszty mogą przekraczać moduł. Dane typu \(a = 7, n = 5\) są traktowane jako \(7 \equiv 2 \pmod 5\); kalkulator automatycznie redukuje ostateczną odpowiedź modulo \(N\).
- Moduły muszą być dodatnimi liczbami całkowitymi. Wartości 0 oraz ujemne są odrzucane.
- Duże układy. Ponieważ \(N\) jest iloczynem wszystkich modułów, rośnie bardzo szybko. Przy wielu modułach występujące liczby mogą przekroczyć zakres, w którym standardowa arytmetyka zmiennoprzecinkowa jest dokładna.
Zastosowania chińskiego twierdzenia o resztach
Poza czystą teorią liczb CRT jest praktycznym narzędziem w wielu dziedzinach. W kryptografii przyspiesza deszyfrowanie RSA, obliczając wyniki modulo każdy czynnik pierwszy osobno i łącząc je ponownie; stanowi też podstawę schematów progowych, takich jak dzielenie sekretu Shamira. W informatyce umożliwia systemy liczbowe rezydualne, wykonujące dodawania i mnożenia równolegle na małych modułach, a pojawia się także w hashowaniu, planowaniu i obliczeniach kalendarzowych — w klasycznych zadaniach typu „liczenie żołnierzy w rzędach”, które pierwotnie zainspirowały pracę Sunzi.
Najczęściej zadawane pytania
Jak rozwiązać układ CRT ręcznie, bez wzoru?
Dla dwóch kongruencji można użyć podstawienia: z pierwszej wynika x = a₁ + k·n₁ dla całkowitych \(k\). Podstaw do drugiej kongruencji, \(a_1 + k n_1 \equiv a_2 \pmod{n_2}\), i rozwiąż ją względem \(k\), znajdując odwrotność \(n_1\) modulo \(n_2\). Następnie wstaw \(k\) z powrotem, aby otrzymać \(x\), i zredukuj modulo \(n_1 n_2\). Ta metoda kolejnych podstawień działa dla dowolnej liczby kongruencji, rozwiązując je po dwie naraz.
Co się stanie, gdy moduły nie są parami względnie pierwsze?
Gdy dwa moduły mają wspólny dzielnik, układ może być niespójny i nie mieć wcale rozwiązania. Rozwiązanie istnieje tylko wtedy, gdy reszty są zgodne: dla każdej pary \(a_i \equiv a_j \pmod{\gcd(n_i, n_j)}\). Jeśli są zgodne, rozwiązanie jest nadal jednoznaczne, ale tylko modulo najmniejszą wspólną wielokrotność modułów, a nie ich iloczyn. Względna pierwszość modułów gwarantuje istnienie rozwiązania — dlatego ten kalkulator odrzuca takie dane.
Dlaczego rozwiązanie jest jednoznaczne i jak znaleźć wszystkie pozostałe rozwiązania?
Jednoznaczność wynika z tego, że jeśli dwie liczby \(x\) i \(x'\) spełniają układ, to ich różnica dzieli się przez każdy moduł, a więc przez ich iloczyn \(N\) (ponieważ są względnie pierwsze). Zatem \(x \equiv x' \pmod{N}\), co oznacza, że w zakresie \(0 \le x < N\) istnieje dokładnie jedno rozwiązanie. Pozostałe rozwiązania to \(x + kN\) dla dowolnej liczby całkowitej \(k\), łącznie z wartościami ujemnymi, np. \(x - N\), jeśli twoje zadanie na nie pozwala.
Czy reszty mogą być ujemne lub większe od modułu?
Tak. Resztę większą od swojego modułu redukuje się automatycznie — na przykład \(a = 7\) przy \(n = 5\) to to samo co \(a = 2\). Reszty ujemne również działają: \(x \equiv -1 \pmod{5}\) znaczy to samo co \(x \equiv 4 \pmod{5}\). Ostateczna odpowiedź jest zawsze znormalizowana do najmniejszego nieujemnego przedstawiciela, w zakresie \(0 \le x < N\).
Jak obliczyć odwrotność modulo ręcznie?
Użyj rozszerzonego algorytmu Euklidesa: wykonaj zwykły algorytm Euklidesa dla \(N_i\) i \(n_i\), a następnie, cofając się, zapisz \(\gcd = 1\) w postaci \(uN_i + vn_i\). Współczynnik \(u\) spełnia \(uN_i \equiv 1 \pmod{n_i}\), zatem \(y_i = u \bmod n_i\). Dla modułu pierwszego \(p\) można też użyć małego twierdzenia Fermata: \(y_i \equiv N_i^{p-2} \pmod{p}\).
Jakie są typowe błędy przy stosowaniu chińskiego twierdzenia o resztach?
Najczęstsze błędy to: użycie modułów, które nie są parami względnie pierwsze (np. 4 i 6, mających wspólny dzielnik 2); pomylenie pól reszty i modułu przy wpisywaniu danych; zapomnienie, że odpowiedź jest całą klasą rozwiązań, a nie pojedynczą liczbą; oraz wpisanie modułu równego 1, co formalnie jest dozwolone, ale nie wnosi żadnej informacji. Sprawdź też, czy reszty odpowiadają twojemu zadaniu — \(x \equiv 2 \pmod{3}\) to nie to samo co \(x \equiv 3 \pmod{2}\).
Czy jest szybki sposób na sprawdzenie odpowiedzi kalkulatora?
Tak — wystarczy podzielić odpowiedź przez każdy moduł i sprawdzić reszty. Jeśli wynikiem jest \(x\), sprawdź, czy \(x \bmod n_i = a_i \bmod n_i\) dla każdej kongruencji w układzie. Drugi sposób: oblicz \(x \bmod N\) inną metodą, np. kolejnymi podstawieniami, i upewnij się, że otrzymujesz tę samą wartość. Jeśli oba testy wypadną pomyślnie, rozwiązanie jest poprawne, bo jednoznaczność modulo \(N\) gwarantuje, że w tym zakresie nie ma innej odpowiedzi.