Chińskie twierdzenie o resztach

Ten artykuł od 2011-02 zawiera treści, przy których brakuje odnośników do źródeł. Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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 ${\displaystyle n_{1},n_{2},\dots ,n_{k}}$ oraz dowolnych liczb całkowitych ${\displaystyle y_{1},y_{2},\dots ,y_{k}}$ istnieje liczba całkowita ${\displaystyle x_{0}}$ spełniająca układ kongruencji

${\displaystyle {\begin{aligned}x&\equiv y_{1}{\pmod {n_{1}}}\\x&\equiv y_{2}{\pmod {n_{2}}}\\&\,\,\,\vdots \\x&\equiv y_{k}{\pmod {n_{k}}}.\end{aligned}}}$

Ponadto, jeśli liczba ${\displaystyle x_{o}\in \mathbb {Z} }$ spełnia powyższy układ, to liczba ${\displaystyle x_{1}\in \mathbb {Z} }$ spełnia ten układ wtedy i tylko wtedy, gdy

${\displaystyle x_{1}\equiv x_{0}{\pmod {n_{1}n_{2}\cdots n_{k}}}.}$^[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

Istnieje algorytm obliczania ${\displaystyle x}$ na podstawie takiego układu równań.

Mianowicie, niech

${\displaystyle M=n_{1}\cdot n_{2}\cdot n_{3}\cdot \ldots \cdot n_{k}}$

oraz ${\displaystyle M_{i}=M/n_{i}(i\leqslant k).}$ Wówczas na podstawie założenia ${\displaystyle n_{i}}$ oraz ${\displaystyle M_{i}}$ są względnie pierwsze, tzn. korzystając z rozszerzonego algorytmu Euklidesa istnieją takie liczby całkowite ${\displaystyle f_{i},g_{i}(i\leqslant k),}$ że

${\displaystyle f_{i}n_{i}+g_{i}M_{i}=1.}$

Niech ${\displaystyle e_{i}=g_{i}M_{i}(i\leqslant k).}$

Wówczas

${\displaystyle e_{i}\equiv 1\ ({\bmod {\ }}n_{i})}$

oraz

${\displaystyle e_{i}\equiv 0\ ({\bmod {\ }}n_{j})}$

gdy ${\displaystyle j\neq i.}$

Wtedy ${\displaystyle x}$ zdefiniowany wzorem

${\displaystyle x=\sum _{i=1}^{k}y_{i}e_{i}}$

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

Przykład

Dany jest układ kongruencji:

${\displaystyle x\equiv 3\ ({\bmod {4}}),}$

${\displaystyle x\equiv 4\ ({\bmod {5}}),}$

${\displaystyle x\equiv 1\ ({\bmod {7}}).}$

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 ${\displaystyle 3+4t}$

Znajdujemy najmniejsze takie ${\displaystyle t,}$ że ${\displaystyle x=3+4t}$ spełnia drugie równanie:

${\displaystyle 3(0),7(1),11(2),15(3),19(4).}$

Najmniejsze takie ${\displaystyle t}$ to ${\displaystyle 4.}$

Z dwóch pierwszych równań otrzymujemy zatem kongruencję ${\displaystyle x\equiv 19({\bmod {2}}0).}$

Ogólne rozwiązanie dwóch pierwszych równań to ${\displaystyle 19+(4\cdot 5)k.}$

Znajdujemy najmniejsze takie ${\displaystyle k,}$ że ${\displaystyle x=19+20k}$ spełnia trzecie równanie:

${\displaystyle 19(0),39(1),59(2),79(3),99(4).}$

Czyli najmniejsze rozwiązanie to ${\displaystyle 99,}$ a ogólne ${\displaystyle 99+(4\cdot 5\cdot 7)r.}$

Uogólnienie

Niech ${\displaystyle R}$ będzie pierścieniem przemiennym z jedynką, a ${\displaystyle I_{1},I_{2},\dots ,I_{n}}$ jego ideałami. Jeśli są one parami względnie pierwsze, tj.

${\displaystyle I_{i}+I_{j}=R,\;(i\neq j,\,i,j\leqslant n),}$

to naturalny homomorfizm

${\displaystyle \phi \colon R\to R/I_{1}\times R/I_{2}\times \ldots \times R/I_{n}}$

zdefiniowany przez warstwy elementu względem ideałów

${\displaystyle \phi (a)=(a+I_{1},a+I_{2},\dots ,a+I_{n})}$

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

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Wydawnictwa Naukowo-Techniczne, 2007.

Literatura dodatkowa

• Donald Knuth: The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, 1997. ISBN 0-201-89684-2.

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., 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].