Chińskie twierdzenie o resztach

Z Wikipedii, wolnej encyklopedii

Chińskie twierdzenie o resztach – jedno z podstawowych twierdzeń w teorii liczb[1], które mówi, że dla dowolnych względnie pierwszych liczb naturalnych oraz dowolnych liczb całkowitych istnieje liczba całkowita spełniająca układ kongruencji

Ponadto, jeśli liczba spełnia powyższy układ, to liczba spełnia ten układ wtedy i tylko wtedy, gdy

[2]

Nazwa twierdzenia związana jest z chińskim matematykiem Sun Zi, który około roku 100 naszej ery rozwiązał problem znajdowania tych liczb całkowitych, które przy dzieleniu przez 3, 5 oraz 7 dają odpowiednio reszty 2, 3 i 2[3].

Algorytm rozwiązywania układu kongruencji[edytuj | edytuj kod]

Istnieje algorytm obliczania na podstawie takiego układu równań.

Mianowicie, niech

oraz Wówczas na podstawie założenia oraz są względnie pierwsze, tzn. korzystając z rozszerzonego algorytmu Euklidesa istnieją takie liczby całkowite że

Niech

Wówczas

oraz

gdy

Wtedy zdefiniowany wzorem

spełnia powyższy układ kongruencji, jest to jedno z rozwiązań – pozostałe różnią się o wielokrotność

Przykład[edytuj | edytuj kod]

Dany jest układ kongruencji:

Używając metody generowania kolejnych wielokrotności (która jest mało wydajnym algorytmem, aczkolwiek prawdopodobnie najlepszym do obliczania ręcznie):

Ogólne rozwiązanie pierwszego równania to
Znajdujemy najmniejsze takie że spełnia drugie równanie:
Najmniejsze takie to
Z dwóch pierwszych równań otrzymujemy zatem kongruencję
Ogólne rozwiązanie dwóch pierwszych równań to
Znajdujemy najmniejsze takie że spełnia trzecie równanie:
Czyli najmniejsze rozwiązanie to a ogólne

Uogólnienie[edytuj | edytuj kod]

Niech będzie pierścieniem przemiennym z jedynką, a jego ideałami. Jeśli są one parami względnie pierwsze, tj.

to naturalny homomorfizm

zdefiniowany przez warstwy elementu względem ideałów

jest epimorfizmem.

Wersja dla liczb wynika z zastosowania twierdzenia do pierścienia liczb całkowitych, będącego pierścieniem ideałów głównych.

Przypisy[edytuj | edytuj kod]

  1. chińskie twierdzenie o resztach, [w:] Encyklopedia PWN [online] [dostęp 2021-10-01].
  2. Jerzy Rutkowski, Teoria liczb w zadaniach, Wydanie I, Warszawa: Wydawnictwo Naukowe PWN, 2018, s. 60, ISBN 978-83-01-19874-9 [dostęp 2024-01-22] (pol.).
  3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein ↓, s. 922.

Bibliografia[edytuj | edytuj kod]

Literatura dodatkowa[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]