Teorema chinezească a resturilor

De la Wikipedia, enciclopedia liberă
Sari la navigare Sari la căutare
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.

Enunț[modificare | modificare sursă]

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: .

Exemplu[modificare | modificare sursă]

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[modificare | modificare sursă]

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 :

Note[modificare | modificare sursă]

  1. ^ Menezes, p. 68

Bibliografie[modificare | modificare sursă]

  • Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott. Handbook of Applied Cryptography.