Chińskie twierdzenie o resztach

Chińskie twierdzenie o resztach – jedno z podstawowych twierdzeń w teorii liczb, które mówi, że dla dowolnych parami względnie pierwszych liczb naturalnych $n_{1},n_{2},\dots ,n_{k}$ oraz dowolnych liczb całkowitych $y_{1},y_{2},\dots ,y_{k}$ istnieje liczba całkowita $x_{0}$ spełniająca układ kongruencji

${\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 $x_{o}\in \mathbb {Z}$ spełnia powyższy układ, to liczba $x_{1}\in \mathbb {Z}$ spełnia ten układ wtedy i tylko wtedy, gdy

$x_{1}\equiv x_{0}{\pmod {n_{1}n_{2}\cdots n_{k}}}.$

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.

Algorytm rozwiązywania układu kongruencji

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

Mianowicie, niech

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

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

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

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

Wówczas

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

oraz

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

gdy $j\neq i.$

Wtedy $x$ zdefiniowany wzorem

$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ść $M.$

Przykład

Dany jest układ kongruencji:

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

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

$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 $3+4t$

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

$3(0),7(1),11(2),15(3),19(4).$

Najmniejsze takie $t$ to $4.$

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

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

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

$19(0),39(1),59(2),79(3),99(4).$

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

Uogólnienie

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

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

to naturalny homomorfizm

$\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

$\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.

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