Chińskie twierdzenie o resztach

twierdzenie o układach kongruencji

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

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

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

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

  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

Literatura dodatkowa edytuj

Linki zewnętrzne edytuj