Chińskie twierdzenie o resztach
Z Wikipedii
Chińskie twierdzenie o resztach mówi, że układ kongruencji:
- ...
gdzie 
są to liczby względnie pierwsze (parami), ma dokładnie jedno nieujemne rozwiązanie mniejsze od 
.
Jest to jedno z najważniejszych twierdzeń w teorii liczb i kryptografii.
Istnieje algorytm wyliczania x na podstawie takiego układu równań.
Mianowicie, niech 
oraz 
, wtedy na podstawie założenia ni oraz Mi są względnie pierwsze, tzn. korzystając z rozszerzonego algorytmu Euklidesa istnieją takie 
, że
Niech ei = giMi.
Wtedy 
oraz 
dla 
. Dlatego x zdefiniowany wzorem
spełnia powyższy układ kongruencji, tzn. jest jego jednym z rozwiązań. Pozostałe różnią się o wielokrotność M.
[edytuj] Przykład
Mamy układ:
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, 7 (2), 11 (1) 15 (0), 19 (4)
- Najmniejsze takie i to 4
- Z dwóch pierwszych równań otrzymujemy zatem
- Ogólne rozwiązanie dwóch pierwszych równań to
- Znajdujemy najmniejsze j, takie że x = 19 + 20j spełnia trzecie równanie:
- 19 (5), 39 (4), 59 (3), 79 (2), 99 (1)
- Czyli najmniejsze rozwiązanie to 99, a ogólne
