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 wiarygodnych źródeł. (Dodanie listy źródeł bibliograficznych lub linków zewnętrznych nie jest wystarczające). 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^[1] mówi, że układ kongruencji:

${\displaystyle x\equiv y_{1}\ ({\bmod {\ }}n_{1}),}$

${\displaystyle x\equiv y_{2}\ ({\bmod {\ }}n_{2}),}$

${\displaystyle \dots }$

${\displaystyle x\equiv y_{k}\ ({\bmod {\ }}n_{k}),}$

(gdzie ${\displaystyle y_{1},y_{2},\dots ,y_{k}}$ są dowolnymi liczbami całkowitymi, a liczby ${\displaystyle n_{1},n_{2},\dots ,n_{k}}$ to liczby parami względnie pierwsze), spełnia dokładnie jedna liczba

${\displaystyle 1\leqslant x\leqslant n_{1}\cdot n_{2}\cdot n_{3}\cdot \ldots \cdot n_{k}}$^[2].

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

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^[2].

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