Chińskie twierdzenie o resztach wyjaśnione

Pewna liczba daje resztę 2 z dzielenia przez 3, resztę 3 z dzielenia przez 5 i resztę 2 z dzielenia przez 7. Jaka to liczba? Sprawdzając liczby po kolei, po chwili dojdziesz do 23, ale w tym pytaniu kryje się twierdzenie: dopóki dzielniki nie mają wspólnego czynnika, poniżej ich iloczynu zawsze jest dokładnie jedna odpowiedź i można ją znaleźć bez zgadywania. Twierdzenie ma około 1500 lat i wciąż pracuje w kalendarzach, w arytmetyce komputerów i w kryptografii, która chroni sieć.

Trzy rzędy znaczników dla liczb dających resztę 2 mod 3, 3 mod 5 i 2 mod 7, spotykających się w jednej kolumnie przy 23
Trzy rzędy znaczników dla liczb dających resztę 2 mod 3, 3 mod 5 i 2 mod 7, spotykających się w jednej kolumnie przy 23

Zadanie z Sunzi Suanjing

Sunzi Suanjing, chińska księga arytmetyki z III–V wieku, pyta o liczbę rzeczy, która liczona po trzy daje resztę 2, po pięć resztę 3, a po siedem resztę 2. Jej odpowiedź to 23, a metoda jest nauczana do dziś: weź 70 za każdą rzecz, która zostaje przy liczeniu po trzy, 21 za każdą przy liczeniu po pięć i 15 za każdą przy liczeniu po siedem, dodaj i odejmuj 105, ile razy się da. 2 × 70 + 3 × 21 + 2 × 15 = 233, a 233 − 2 × 105 = 23. Wiersz z epoki Ming przez wieki utrwalał w pamięci liczby 70, 21, 15 i 105. Qin Jiushao podał ogólną metodę w 1247 roku, to samo zadanie występuje w Liber Abaci Fibonacciego z 1202 roku, a Carl Friedrich Gauss sformułował twierdzenie we współczesnej postaci w Disquisitiones Arithmeticae z 1801 roku.

Strona z wydania z czasów Qing księgi Sunzi Suanjing, chińskiego traktatu arytmetycznego z III–V wieku, który pyta o liczbę dającą reszty 2, 3 i 2 przy liczeniu trójkami, piątkami i siódemkami.
Strona z wydania z czasów Qing księgi Sunzi Suanjing, chińskiego traktatu arytmetycznego z III–V wieku, który pyta o liczbę dającą reszty 2, 3 i 2 przy liczeniu trójkami, piątkami i siódemkami.
Carl Friedrich Gauss na portracie Christiana Albrechta Jensena z 1840 roku. Notację kongruencji a ≡ b (mod n) wprowadził w Disquisitiones Arithmeticae z 1801.
Carl Friedrich Gauss na portracie Christiana Albrechta Jensena z 1840 roku. Notację kongruencji a ≡ b (mod n) wprowadził w Disquisitiones Arithmeticae z 1801.

Co mówi twierdzenie

Weź moduły n₁, n₂, …, nₖ, z których żadne dwa nie mają wspólnego dzielnika, i dowolne reszty a₁, a₂, …, aₖ. Wtedy istnieje dokładnie jedna liczba całkowita x od 0 do N − 1, gdzie N = n₁ × n₂ × … × nₖ, która z dzielenia przez nᵢ daje resztę aᵢ dla każdego i. Wszystkie inne rozwiązania różnią się od niej o wielokrotność N. W zapisie arytmetyki modularnej: układ x ≡ aᵢ (mod nᵢ) ma rozwiązanie i jest ono jednoznaczne mod N. Inaczej mówiąc, liczba od 0 do N − 1 i lista jej reszt niosą dokładnie tę samą informację: 3 × 5 × 7 = 105 liczb i 3 × 5 × 7 = 105 możliwych list reszt, każda użyta raz.

Budowanie rozwiązania

Liczby 70, 21 i 15 nie są magiczne. Każda z nich daje resztę 1 z dzielenia przez swój moduł i resztę 0 z dzielenia przez pozostałe: 70 = 2 × 35 jest wielokrotnością 5 i 7 i daje resztę 1 z dzielenia przez 3. Ogólnie bierze się Nᵢ = N / nᵢ, wielokrotność każdego modułu oprócz nᵢ, i mnoży przez yᵢ, odwrotność Nᵢ mod nᵢ. Odwrotność istnieje, bo Nᵢ i nᵢ nie mają wspólnego dzielnika, a rozszerzony algorytm Euklidesa ją znajduje: wykonuje dzielenia Euklidesa dla największego wspólnego dzielnika i cofa się do tożsamości Bézouta 1 = s × nᵢ + t × Nᵢ, tak że t jest odwrotnością. Wtedy x = a₁N₁y₁ + a₂N₂y₂ + …, zredukowane mod N, pasuje do każdego równania, bo każdy składnik pasuje do swojego równania i znika we wszystkich pozostałych.

Równanie po równaniu

Jest drugi sposób, który nie wymaga iloczynu wszystkich modułów. Każde rozwiązanie x ≡ 2 (mod 3) ma postać x = 2 + 3t. Po podstawieniu do następnego równania dostajemy 2 + 3t ≡ 3 (mod 5), czyli 3t ≡ 1 (mod 5), a pomnożenie przez 2, odwrotność 3 mod 5, daje t ≡ 2 (mod 5). Wtedy x = 2 + 3 × 2 = 8, a dwa pierwsze równania razem mówią, że x ≡ 8 (mod 15). Powtarzając to z trzecim równaniem, 8 + 15t ≡ 2 (mod 7) daje t ≡ 1, więc x ≡ 23 (mod 105). Takie podstawianie utrzymuje mniejsze liczby, w ten sposób komputer zwykle rozwiązuje takie układy i działa ono także wtedy, gdy moduły mają wspólny dzielnik.

Moduły ze wspólnym dzielnikiem

Jeśli dwa moduły mają wspólny dzielnik, ich równania nakładają się na siebie: x ≡ 1 (mod 4) mówi już, że x jest nieparzyste, a x ≡ 4 (mod 6) mówi, że x jest parzyste, więc żadne x nie spełnia obu. Ogólnie x ≡ a (mod m) i x ≡ b (mod n) mogą zachodzić jednocześnie dokładnie wtedy, gdy a i b dają tę samą resztę z dzielenia przez g = gcd(m, n), czyli gdy g dzieli a − b. Rozwiązanie jest wtedy jednoznaczne mod lcm(m, n) = m × n / g, a nie mod m × n. Stara zagadka o koszu jajek, z którego przy wyjmowaniu po 2, 3, 4, 5 lub 6 zostaje 1, a przy wyjmowaniu po 7 nie zostaje nic, ma odpowiedź 301, powtarzającą się co 420 = lcm(2, 3, 4, 5, 6, 7). Układ ma rozwiązanie dokładnie wtedy, gdy każde dwa jego równania są zgodne, więc układ sprzeczny zawsze zawiera parę, która się wyklucza.

Kalendarze, komputery i RSA

W 1583 roku Joseph Scaliger połączył trzy cykle kalendarzowe, 28-letni cykl słoneczny, 19-letni cykl księżycowy i 15-letnią indykcję, w okres juliański liczący 28 × 19 × 15 = 7980 lat. Z twierdzenia wynika, że każdy rok ma własną kombinację trzech numerów cyklu, a okres zaczyna się w 4713 roku p.n.e., ostatnim roku, w którym wszystkie trzy wynosiły 1; astronomowie wciąż liczą od niego dni juliańskie. Komputery używają twierdzenia, by liczyć na ogromnych liczbach zapisanych jako listy małych reszt, które można dodawać i mnożyć osobno i równolegle, a na końcu połączyć. Deszyfrowanie RSA działa tak samo: c^d mod n przy n = p × q liczy się jako dwie potęgi mod p i mod q połączone twierdzeniem, mniej więcej cztery razy szybciej niż jedną potęgę mod n. Schematy dzielenia sekretu, takie jak schematy Mignotte'a oraz Asmutha i Blooma, ukrywają sekret w resztach tak, że ujawnia go dopiero wystarczająco wiele z nich naraz.

Ron Rivest, Adi Shamir i Len Adleman (od lewej do prawej)
Ron Rivest, Adi Shamir i Len Adleman (od lewej do prawej)

Wypróbuj sam

Otwórz kalkulator, aby wpisać dowolny układ kongruencji, do 20 równań i liczby mające najwyżej 200 cyfr, albo wybierz jeden z rozwiązanych przykładów: zadanie Sunzi, kosz jajek, okres juliański, dwa rozkłady jazdy autobusów, deszyfrowanie RSA i układ bez rozwiązania. Obliczenia są rozpisane na Twoich liczbach, konstrukcją albo przez podstawianie, z rozszerzonym algorytmem Euklidesa dla każdej odwrotności. Rysunek zaznacza liczby spełniające każde równanie, tak że widać jedyną kolumnę, w której spotykają się wszystkie, albo rozkłada reszty dwóch równań w tabeli, w której każda liczba ma własną komórkę.

Często zadawane pytania

Czy rozwiązanie układu kongruencji jest jednoznaczne?

Tylko z dokładnością do wielokrotności modułu. Jeśli x = 23 rozwiązuje zadanie Sunzi, to rozwiązują je też 23 + 105 = 128, 233 i −82, bo dodanie 105 nie zmienia żadnej reszty. Twierdzenie mówi, że istnieje dokładnie jedno rozwiązanie od 0 do 104; przy modułach o wspólnych dzielnikach dokładnie jedno poniżej ich najmniejszej wspólnej wielokrotności.

Dlaczego moduły muszą być względnie pierwsze?

W konstrukcji dlatego, że Nᵢ musi mieć odwrotność mod nᵢ, a ta istnieje tylko wtedy, gdy nie mają wspólnego dzielnika. W samym twierdzeniu dlatego, że wspólne dzielniki sprawiają, że niektóre równania się nakładają: wtedy układ albo nie ma rozwiązania, albo ma mniej różnych rozwiązań, a rozwiązania powtarzają się co najmniejszą wspólną wielokrotność zamiast co iloczyn.

Jak znaleźć odwrotność modularną ręcznie?

Rozszerzonym algorytmem Euklidesa. Dla odwrotności 15 mod 7: 15 = 2 × 7 + 1, więc 1 = 15 − 2 × 7 i 15 × 1 ≡ 1 (mod 7): odwrotność to 1. Dla 35 mod 3: 35 = 11 × 3 + 2 i 3 = 1 × 2 + 1, więc 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, a odwrotność 35 mod 3 to −1 ≡ 2. Przy małych modułach można też po prostu sprawdzać 1, 2, 3, …, aż iloczyn da resztę 1.

Co twierdzenie ma wspólnego z zegarami?

Reszta mod n to pozycja na zegarze o n godzinach. Dwa zegary o 3 i 5 godzinach, uruchomione razem i przesuwane o godzinę naraz, pokazują każdą z 15 par pozycji jeden raz, zanim wrócą na start, bo 3 i 5 nie mają wspólnego dzielnika. Zegary o 4 i 6 godzinach wracają po 12 krokach i pokazują tylko 12 z 24 par: pozycja nieparzysta i parzysta nigdy nie występują razem.

Chcesz wypróbować?

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

Otwórz kalkulator chińskiego twierdzenia o resztach