MatematykaLiczby — dziwne własności rzeczy pozornie najprostszych

Kilka reszt z dzielenia może jednoznacznie odtworzyć całą liczbę

Reszta z dzielenia wygląda jak brutalna utrata informacji: jeśli wiemy tylko, że liczba daje resztę 2 przy dzieleniu przez 3, pasuje nieskończenie wiele liczb. Chińskie twierdzenie o resztach pokazuje jednak, że odpowiednio dobrany zestaw takich „niepełnych” informacji może razem określić liczbę jednoznacznie w dużym zakresie. Jeśli moduły są parami względnie pierwsze, układ reszt ma dokładnie jedno rozwiązanie modulo iloczynu modułów. Dla przykładu reszty modulo 3, 5 i 7 wspólnie identyfikują jedną klasę spośród 105 możliwości.

Każda reszta osobno mówi bardzo mało

Warunek x≡2 mod 3 oznacza tylko, że x należy do ciągu …, 2, 5, 8, 11, 14, …. Dodanie warunku modulo 5 zawęża możliwości, ale nadal pozostawia nieskończenie wiele liczb. Zaskoczenie pojawia się wtedy, gdy moduły są parami względnie pierwsze. Dla 3, 5 i 7 ich iloczyn wynosi 105, a kombinacja trzech reszt wybiera dokładnie jedną pozycję wśród klas od 0 do 104. Wszystkie pozostałe rozwiązania różnią się od niej o wielokrotność 105.

Treść chińskiego twierdzenia o resztach

Jeśli m1,…,mk są parami względnie pierwsze, to dla dowolnych zadanych reszt a1,…,ak układ x≡ai mod mi ma rozwiązanie. Co więcej, rozwiązanie jest jednoznaczne modulo M=m1·m2·…·mk. To znaczy, że w jednym pełnym zakresie długości M nie ma dwóch różnych liczb dających dokładnie ten sam komplet reszt. Zestaw lokalnych informacji działa więc jak kod współrzędnych liczby.

Przykład: 2, 3, 2

Klasyczny przykład pyta o liczbę, która daje resztę 2 modulo 3, resztę 3 modulo 5 oraz resztę 2 modulo 7. Jednym rozwiązaniem jest 23: 23=7·3+2, 23=4·5+3 i 23=3·7+2. Twierdzenie mówi, że w zakresie modulo 105 to rozwiązanie jest jedyne. Kolejne rozwiązania to 23+105k. Trzy niewielkie reszty wystarczają więc do rozróżnienia wszystkich 105 klas.

Od starożytnego problemu do obliczeń

Twierdzenie jest ważne nie tylko jako elegancka własność liczb. Pozwala rozbijać rachunki modulo dużego iloczynu na kilka niezależnych rachunków modulo mniejszych liczb, a potem składać wyniki. Taki sposób myślenia pojawia się w algorytmach, arytmetyce komputerowej i kryptografii. Sedno pozostaje jednak czysto matematyczne: informacja, która osobno jest bardzo nieprecyzyjna, może po odpowiednim połączeniu stać się kompletna.

Jak zbudować rozwiązanie zamiast go zgadywać

Twierdzenie nie jest tylko zapewnieniem, że rozwiązanie gdzieś istnieje. Ma konstruktywny dowód. Dla każdego modułu mi bierzemy M/mi, czyli iloczyn pozostałych modułów. Ta liczba jest podzielna przez wszystkie pozostałe moduły, a ponieważ moduły są parami względnie pierwsze, ma odwrotność modulo mi. Po pomnożeniu przez tę odwrotność otrzymujemy składnik, który daje 1 modulo mi i 0 modulo wszystkich pozostałych modułów. Odpowiednia suma takich składników, przemnożonych przez żądane reszty ai, daje rozwiązanie całego układu. To matematyczny odpowiednik składania sygnału z niezależnych kanałów: każdy element konstrukcji odpowiada za jedną współrzędną i nie zakłóca innych. Dzięki temu twierdzenie jest zarówno eleganckie, jak i algorytmiczne.

Warunek względnej pierwszości jest kluczowy

Jeśli moduły nie są parami względnie pierwsze, sytuacja może wyglądać inaczej: układ może nie mieć rozwiązania albo może nie być jednoznaczny modulo prostego iloczynu. Na przykład wymagania x≡0 mod 2 oraz x≡1 mod 4 są sprzeczne, bo każda liczba podzielna przez 4 jest też parzysta. Standardowa wersja chińskiego twierdzenia o resztach usuwa takie konflikty przez założenie wzajemnej względnej pierwszości modułów. Dzięki temu każda kombinacja reszt jest dopuszczalna i tworzy dokładnie jedną klasę modulo iloczynu.

Reszty działają jak współrzędne liczby

Można myśleć o liczbie modulo M jako o punkcie opisanym kilkoma współrzędnymi: jej resztami modulo m1,m2,…,mk. Przy parami względnie pierwszych modułach przejście między „jedną dużą współrzędną” modulo M a zestawem małych reszt jest odwracalne. To dokładnie powód, dla którego twierdzenie jest tak użyteczne obliczeniowo. Zamiast wykonywać trudną operację na dużych liczbach, można czasem policzyć kilka mniejszych wyników niezależnie, a na końcu bez utraty informacji złożyć je z powrotem w jeden wynik.

#chińskie twierdzenie o resztach#kodowanie informacji#kongruencje#modulo#teoria liczb
Źródła i weryfikacja
Otrzymuj codzienne losowe ciekawostki