Chińskie twierdzenie o resztach
![]() |
Ten artykuł od 2011-02 zawiera treści, przy których brakuje odnośników do źródeł. |
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
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]- ↑ chińskie twierdzenie o resztach, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-10-01] .
- ↑ 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.).
- ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein ↓, s. 922.
Bibliografia
[edytuj | edytuj kod]- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Wydawnictwa Naukowo-Techniczne, 2007.
Literatura dodatkowa
[edytuj | edytuj kod]- Donald Knuth: The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, 1997. ISBN 0-201-89684-2.
Linki zewnętrzne
[edytuj | edytuj kod]- Eric W. Weisstein , Chinese Remainder Theorem, [w:] MathWorld, Wolfram Research (ang.). [dostęp 2023-08-10].
Chinese remainder theorem (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2023-08-10].