Chińskie twierdzenie o resztach

Jedno z zasadniczych twierdzeń, wiążące własności liczby całkowitej n z własnościami jej czynników w rozkładzie na iloczyn potęg liczb pierwszych, jest bardzo stare twierdzenie noszące nazwę chińskiego twierdzenia o resztach.

Jeśli liczby całkowite dodatnie n₁, n₂, n₃, ... , n_k są parami względnie pierwsze, zaś a₁, a₂, a₃, ... , a_k są dowolnymi liczbami całkowitymi, to istnieje taka liczba całkowita a, że:

a ≡ a₁(mod n₁),
a ≡ a₂(mod n₂),
...........................
a ≡ a_k(mod n_k),

Około roku 100 n.e. chiński matematyk Sun-Tsu rozwiązał problem znajdowania tych liczb całkowitych, które przy dzieleniu przez 3, 5 i 7 dają reszty, odpowiednio, 2, 3 i 2. Jednym z takich rozwiązań jest n = 23, pozostałe są postaci 23 + 105 · k dla dowolnej liczby całkowitej k.

Chińskie twierdzenie o resztach ma wiele zastosowań. W rzeczywistości chińscy generałowie stosowali je do sprawdzania liczby swoich żołnierzy, wydając kolejno rozkazy: W dwuszeregu zbiórka! W 3-szeregu zbiórka! W 5-szeregu zbiórka! i kontynuowali w ten sposób, obliczając za każdym razem tylko resztę, czyli liczbę żołnierzy w ostatniej niepełnej kolumnie.

Chińskie twierdzenie o resztach wskazuje również zależność między układem równań modulo pewien zbiór liczb parami względnie pierwszych, a równaniem modulo ich iloczyn.