Formularea originală a lui
Sun-tzu: sistemul:

Are o infinitate de soluții

, unde

Teorema chinezească a resturilor este un rezultat provenit din teoria numerelor, cu aplicații în criptografie. Teorema a fost cunoscută de matematicienii chinezi din secolul al III-lea, apărând într-o carte a matematicianului Sun Tzu, iar apoi, în 1247, într-o altă carte a lui Qin Jiushao.
Dacă
sunt numere întregi prime între ele două câte două, atunci, pentru orice numere întregi
, există un număr întreg
care este soluție a următorului sistem de congruențe[1]:

Pentru a rezolva sistemul, definim mai întâi notația
drept inversul modular al lui
în raport cu
, unde
. Dacă
, oricare ar fi
, unde
, atunci
. Pentru a verifica corectitudinea soluției propuse, se poate observa că fiecare termen
din sumă este congruent cu
, deoarece
. De asemenea, toți ceilalți termeni
, unde
, conțin elementul
care este multiplu de
, motiv pentru care se vor anula. Astfel, sistemul inițial se verifică. Mai mult, sistemul are o infinitate de soluții:
.
Să considerăm sistemul:
Conform formulei
, soluția se va calcula drept:
. Pornind de la această soluție, putem găsi o infinitate de alte soluții:
.
Relația
, unde
este validă dacă și numai dacă
; de aceea, sistemul de congruențe poate fi rezolvat chiar dacă numerele
nu sunt prime între ele două câte două, cu condiția:
Toate soluțiile
vor fi atunci congruente modulo cel mai mic multiplu comun al numerelor
:
- Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott. Handbook of Applied Cryptography.