Otwórz menu główne

Chińskie twierdzenie o resztach

Chińskie twierdzenie o resztach mówi, że układ kongruencji:

(gdzie są dowolnymi liczbami całkowitymi, a liczby to liczby parami względnie pierwsze), spełnia dokładnie jedna liczba

[1].

Jest to jedno z najważniejszych twierdzeń w teorii liczb i kryptografii.

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[1].

Spis treści

Algorytm rozwiązywania układu kongruencjiEdytuj

Istnieje algorytm wyliczania   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ładEdytuj

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ólnienieEdytuj

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.

PrzypisyEdytuj

BibliografiaEdytuj