Kalkulator chińskiego twierdzenia o resztach
Policz stos rzeczy po trzy, a zostaną 2, po pięć zostaną 3, po siedem zostaną 2: jest ich 23, albo 128, albo 233, jedna odpowiedź co 105. To zadanie z Sunzi Suanjing, od którego chińskie twierdzenie o resztach wzięło nazwę. Wpisz dowolny układ kongruencji x ≡ a (mod n), z tyloma równaniami i tak dużymi liczbami, jak chcesz, i zobacz odpowiedź, obliczenia na Twoich liczbach oraz rysunek pokazujący, dlaczego to działa. Gdy równania nie mogą być spełnione wszystkie naraz, kalkulator wskazuje dwa sprzeczne i pokazuje dlaczego. Wpisz równania x ≡ a (mod n), po jednym w wierszu: a to reszta, a n to moduł. Dodaj wiersz przyciskiem Dodaj równanie albo klawiszem Enter w ostatnim module, a usuń go przyciskiem ×. Działają liczby całkowite do 200 cyfr, a a może być ujemne. Możesz też wybrać rozwiązany przykład. Kafelki pokazują najmniejsze rozwiązanie i co ile się powtarza; pod nimi są pierwsze rozwiązania dodatnie i sprawdzenie każdego równania. Rysunek zaznacza liczby spełniające każde równanie, a kolumna, w której każdy wiersz ma znacznik, to rozwiązanie; tabela reszt pokazuje dwa równania naraz. Obliczenia są rozpisane na Twoich liczbach, konstrukcją podręcznikową albo przez podstawianie.
Jak to działa
- Wpisz równania x ≡ a (mod n), po jednym w wierszu, albo wybierz rozwiązany przykład, taki jak zadanie Sunzi, kosz jajek lub okres juliański.
- Odczytaj najmniejsze rozwiązanie, moduł, z jakim się powtarza, i pierwsze rozwiązania dodatnie, każde sprawdzone w każdym równaniu.
- Śledź obliczenia krok po kroku, konstrukcją albo przez podstawianie, i przełączaj rysunek między osią liczbową a tabelą reszt.
Jak działa konstrukcja
Gdy żadne dwa moduły nie mają wspólnego dzielnika, rozwiązanie można zbudować wprost. Pomnóż moduły: w zadaniu Sunzi N = 3 × 5 × 7 = 105. Dla każdego równania weź Nᵢ = N / nᵢ, wielokrotność każdego innego modułu: 35, 21 i 15. Następnie znajdź odwrotność yᵢ liczby Nᵢ mod nᵢ rozszerzonym algorytmem Euklidesa: 35 daje resztę 2 z dzielenia przez 3, a 2 × 2 = 4 ≡ 1 (mod 3), więc y₁ = 2; 21 i 15 dają resztę 1, więc ich odwrotności to 1. Teraz x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, a 233 mod 105 = 23. Każdy składnik pasuje do swojego równania i jest wielokrotnością pozostałych modułów, więc suma pasuje do wszystkich.
Gdy moduły mają wspólny dzielnik
Układ, którego moduły mają wspólne dzielniki, też może mieć rozwiązanie. Dwa równania x ≡ a (mod m) i x ≡ b (mod n) mogą być spełnione jednocześnie dokładnie wtedy, gdy a − b jest wielokrotnością gcd(m, n), a rozwiązanie powtarza się wtedy co lcm(m, n) zamiast co m × n. Dwa autobusy odjeżdżające w minucie 5 i 11, co 12 i co 18 minut, spotykają się w minucie 29, a potem co 36 minut, bo 11 − 5 = 6 jest wielokrotnością gcd(12, 18) = 6. Ale x ≡ 1 (mod 4) i x ≡ 4 (mod 6) nigdy nie mogą zachodzić razem: pierwsze czyni x nieparzystym, a drugie parzystym. Cały układ ma rozwiązanie dokładnie wtedy, gdy ma je każda para jego równań, i właśnie tak kalkulator znajduje dwa sprzeczne.
Często zadawane pytania
Co mówi chińskie twierdzenie o resztach?
Jeśli żadne dwa z modułów n₁, n₂, … nie mają wspólnego dzielnika, to dla dowolnych reszt a₁, a₂, … istnieje dokładnie jedno x od 0 do N − 1 takie, że x ≡ aᵢ (mod nᵢ) dla każdego i, gdzie N to iloczyn modułów. Każde inne rozwiązanie różni się od niego o wielokrotność N: w zadaniu Sunzi rozwiązania to 23, 128, 233 i tak dalej, jedno co 105.
Dlaczego nazywa się chińskie?
Najstarsze znane zadanie tego rodzaju pochodzi z Sunzi Suanjing, chińskiej księgi arytmetyki napisanej między III a V wiekiem: liczone po trzy, po pięć i po siedem, pewne rzeczy dają reszty 2, 3 i 2. Qin Jiushao podał ogólną metodę dla takich zadań w 1247 roku, a Carl Friedrich Gauss sformułował twierdzenie we współczesnej postaci w 1801 roku.
A jeśli moduły nie są względnie pierwsze?
Wtedy rozwiązania może nie być, a jeśli jest, powtarza się co najmniejszą wspólną wielokrotność modułów zamiast co ich iloczyn. Dwa równania są zgodne, gdy ich reszty są równe modulo gcd ich modułów. Zagadka z jajkami używa liczb 2, 3, 4, 5, 6 i 7, które mają wspólne dzielniki, a mimo to ma rozwiązanie: 301, powtarzające się co 420.
Jak RSA korzysta z chińskiego twierdzenia o resztach?
Odszyfrowanie wiadomości RSA to obliczenie c^d mod n, gdzie n = p × q. Szybciej jest obliczyć osobno c^d mod p i c^d mod q, z wykładnikiem zredukowanym mod p − 1 i q − 1, i połączyć oba wyniki twierdzeniem. Przy liczbach o połowę krótszych każda z dwóch potęg kosztuje około jednej ósmej pracy, więc deszyfrowanie jest mniej więcej cztery razy szybsze i większość oprogramowania RSA tak właśnie robi.
Jak duże mogą być liczby?
Do 20 równań, z liczbami mającymi najwyżej 200 cyfr każda. Kalkulator liczy na dokładnych liczbach całkowitych w Twojej przeglądarce, więc odpowiedź jest dokładna bez względu na długość i 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