Chińskie twierdzenie o resztach

Szablon:Dopracować 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{array}{cc}x& \equiv y_1(\mathrm{mod}{n}_1)\\ x& \equiv y_2(\mathrm{mod}{n}_2)\\ & ⋮\\ x& \equiv y_k(\mathrm{mod}{n}_k).\end{array}$

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(\mathrm{mod}{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 2Szablon:Odn.

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 \dots \cdot n_k$

oraz $M_i=M/n_i(i⩽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⩽k),$ że

$f_i{n}_i+g_i{M}_i=1.$

Niech $e_i=g_i{M}_i(i⩽k).$

Wówczas

$e_i\equiv 1(mod{n}_i)$

oraz

$e_i\equiv 0(mod{n}_j)$

gdy $j\ne 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(mod4),$

$x\equiv 4(mod5),$

$x\equiv 1(mod7).$

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(mod20).$

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\ne j,i,j⩽n),$

to naturalny homomorfizm

$\varphi :R\to R/I_1\times R/I_2\times \dots \times R/I_n$

zdefiniowany przez warstwy elementu względem ideałów

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

• Szablon:Cytuj książkę

Literatura dodatkowa

• Szablon:Cytuj książkę

Linki zewnętrzne

• Szablon:MathWorld [dostęp 2023-08-10].
• Szablon:Otwarty dostęp Chinese remainder theorem Szablon:Lang, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2023-08-10].