Chińskie twierdzenie o resztach

Chińskie twierdzenie o resztach mówi, że układ kongruencji:

$x \equiv y_1\ (\bmod\ n_1)$

$x \equiv y_2\ (\bmod\ n_2)$

...

$x \equiv y_k\ (\bmod\ n_k)$

(gdzie $y_1,y_2, \dots, y_k$ są dowolnymi liczbami całkowitymi, a $n_1, n_2, \dots, n_k$ to liczby parami względnie pierwsze)

spełnia dokładnie jedna liczba $1 \leq x \leq n_1n_2n_3 \cdots n_k$.

Jest to jedno z najważniejszych twierdzeń w teorii liczb i kryptografii.

Algorytm rozwiązywania układu kongruencji

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

Mianowicie, niech $M = n_1n_2\dots n_k$ oraz $M_i = \frac{M}{n_i}$, wtedy na podstawie założenia $n_i$ oraz $M_i$ są względnie pierwsze, tzn. korzystając z rozszerzonego algorytmu Euklidesa istnieją takie $f_i,\ g_i \in \Z$, że $f_i n_i + g_i M_i = 1$.

Niech $e_i = g_i M_i$. Wówczas $e_i \equiv 1\ (\bmod\ n_i)$ oraz $e_i \equiv 0\ (\bmod\ n_j)$ dla $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 rozwiazań - pozostałe różnią się o wielokrotność $M$.

Przykład

Mamy układ:

$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 liczenia na kartce):

Ogólne rozwiązanie pierwszego równania to $3+4i$

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

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

Najmniejsze takie $i$ to 4

Z dwóch pierwszych równań otrzymujemy zatem $x \equiv 19 \ (\bmod 20)$

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

Znajdujemy najmniejsze $j$, takie że $x=19+20j$ 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 \times 5 \times 7)k$

Uogólnienie

Niech $R$ będzie pierścieniem przemiennym z jedynką, a $I_1,I_2, \ldots ,I_n$ jego ideałami. Jeśli są one parami względnie pierwsze ($I_i+I_j=R$), to naturalny homomorfizm $\phi : R \rightarrow R/I_1 \times R/I_2 \times \cdots \times R/I_n$ zdefiniowany przez warstwy elementu względem ideałów $\phi (a) = (a+I_1, a+I_2, \ldots, a+I_n)$ jest epimorfizmem.

Wersja dla liczb wynika z zastosowania twierdzenia do pierścienia $\mathbb{Z}$ i skorzystania z własności ideałów w pierścieniach głównych.