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 oraz dowolnych liczb całkowitych istnieje liczba całkowita spełniająca układ kongruencji
Ponadto, jeśli liczba spełnia powyższy układ, to liczba spełnia ten układ wtedy i tylko wtedy, gdy
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.
Algorytm rozwiązywania układu kongruencji Istnieje algorytm obliczania na podstawie takiego układu równań.
Mianowicie, niech
oraz Wówczas na podstawie założenia oraz są względnie pierwsze, tzn. korzystając z rozszerzonego algorytmu Euklidesa istnieją takie liczby całkowite że
Niech
Wówczas
oraz
gdy
Wtedy zdefiniowany wzorem
spełnia powyższy układ kongruencji, jest to jedno z rozwiązań – pozostałe różnią się o wielokrotność
Przykład Dany jest układ kongruencji: