Reklama

Chińskie twierdzenie o resztach

Chińskie twierdzenie o resztach to kluczowe twierdzenie w teorii liczb, które stwierdza, że dla dowolnych 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:

Reklama

$\begin{align}
x &\equiv y_1 \pmod{n_1} \\
x &\equiv y_2 \pmod{n_2} \\
&\,\,\,\vdots \\
x &\equiv y_k \pmod{n_k}.
\end{align}$

Jeśli $x_0$ spełnia ten układ, to każda inna liczba $x_1$ również spełnia, jeśli zachodzi:

Reklama

$x_1 \equiv x_0 \pmod{n_1 n_2 \cdots n_k}.$

Twierdzenie nazwane jest na cześć chińskiego matematyka Sun Zi, który w I wieku n.e. rozwiązał problem związany z resztami przy dzieleniu przez 3, 5 i 7.

Algorytm rozwiązywania układu kongruencji

Aby obliczyć $x$ na podstawie układu kongruencji, stosujemy następujące kroki:

Obliczamy $M = n_1 \cdot n_2 \cdots n_k$ .
Dla każdego $i obliczamy M_i = M/n_i .$
Stosując rozszerzony algorytm Euklidesa, znajdujemy liczby całkowite $f_i, g_i$ , takie że $f_i n_i + g_i M_i = 1$ .
Definiujemy e_i = g_i M_i, które spełniają:
- $e_i \equiv 1\ (\bmod\ n_i)$
- $e_i \equiv 0\ (\bmod\ n_j)$ dla $j \neq i$ .
Obliczamy $x = \sum_{i=1}^k y_i e_i$ , które spełnia układ kongruencji.

Wszystkie inne rozwiązania różnią się od siebie wielokrotnościami $M$ .

Przykład

Rozważmy układ kongruencji:

$\begin{align}
x &\equiv 3 \ (\bmod 4), \\
x &\equiv 4 \ (\bmod 5), \\
x &\equiv 1 \ (\bmod 7).
\end{align}$

Rozwiązując, otrzymujemy:

Ogólne rozwiązanie pierwszego równania to $3 + 4t$ .
Najmniejsze $t$ dla drugiego równania to $4$ , co daje $x \equiv 19 \ (\bmod 20)$ .
Ostateczne rozwiązanie to $99 + (4 \cdot 5 \cdot 7)r$ .