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 Sunzi în Sunzi Suanjing, iar apoi, în 1247, într-o altă carte a lui Qin Jiushao.
Enunț
Dacă sunt numere întregiprime î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: .
Exemplu
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: .
Generalizare
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: