Chińskie twierdzenie o resztach

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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

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

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ł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]

Bibliografia[edytuj | edytuj kod]