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.

Dacă ${\displaystyle m_{1},m_{2},...,m_{n))$ sunt numere întregi prime între ele două câte două, atunci, pentru orice numere întregi ${\displaystyle a_{1},a_{2},...,a_{n))$, există un număr întreg ${\displaystyle x}$ care este soluție a următorului sistem de congruențe^[1]:

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {m_{1))}\\x&\equiv a_{2}{\pmod {m_{2))}\\&\vdots \\x&\equiv a_{k}{\pmod {m_{k))}\end{aligned))}$

Pentru a rezolva sistemul, definim mai întâi notația ${\displaystyle x_{m}^{-1))$drept inversul modular al lui ${\displaystyle x}$ în raport cu ${\displaystyle m}$, unde ${\displaystyle x,m\in \mathbb {Z} }$. Dacă ${\displaystyle X_{k}={\frac {M}{m_{k))))$, oricare ar fi ${\displaystyle k={\overline {1,n))}$, unde ${\displaystyle M={m_{1}*m_{2}*...*m_{n))}$, atunci ${\displaystyle x=a_{1}X_{1}{X_{1))_{m_{1))^{-1}+a_{2}X_{2}{X_{2))_{m_{2))^{-1}+...+a_{n}X_{n}{X_{n))_{m_{n))^{-1}=\sum _{k=1}^{n}{a_{k}X_{k}{X_{k))_{m_{k))^{-1))}$. Pentru a verifica corectitudinea soluției propuse, se poate observa că fiecare termen ${\displaystyle {a_{k}X_{k}{X_{k))_{m_{k))^{-1))}$ din sumă este congruent cu ${\displaystyle a_{k}({\text{mod ))m_{k})}$, deoarece ${\displaystyle {X_{k}{X_{k))_{m_{k))^{-1))\equiv 1({\text{mod ))m_{k})}$. De asemenea, toți ceilalți termeni ${\displaystyle {a_{i}X_{i}{X_{i))_{m_{i))^{-1))}$, unde ${\displaystyle i\neq k}$, conțin elementul ${\displaystyle X_{i}={\frac {m_{1}m_{2}...m_{n)){m_{i))))$ care este multiplu de ${\displaystyle m_{k))$, motiv pentru care se vor anula. Astfel, sistemul inițial se verifică. Mai mult, sistemul are o infinitate de soluții: ${\displaystyle S=\{x+kM\,\,|\,\,k\in \mathbb {Z} \))$.

Să considerăm sistemul:

${\displaystyle {\begin{aligned}x&\equiv 3{\pmod {5))\\x&\equiv 4{\pmod {7))\\x&\equiv 2{\pmod {3))\end{aligned))}$

Conform formulei ${\displaystyle x=\sum _{k=1}^{n}{a_{k}X_{k}{X_{k))_{m_{k))^{-1))}$, soluția se va calcula drept: ${\displaystyle x=3*21*1+4*15*1+2*35*2=263}$. Pornind de la această soluție, putem găsi o infinitate de alte soluții: ${\displaystyle x=263+105k}$.

Relația ${\displaystyle x\equiv y{\pmod {m_{i))))$, unde ${\displaystyle 1\leq i\leq n}$ este validă dacă și numai dacă ${\displaystyle x\equiv y{\pmod {M))}$; de aceea, sistemul de congruențe poate fi rezolvat chiar dacă numerele ${\displaystyle m_{i))$ nu sunt prime între ele două câte două, cu condiția:

${\displaystyle a_{i}\equiv a_{j}{\pmod {cmmdc(m_{i},m_{j})))\,\,\,\,\forall \,1\leq i,\,j\leq n\,\!}$

Toate soluțiile ${\displaystyle x}$ vor fi atunci congruente modulo cel mai mic multiplu comun al numerelor ${\displaystyle m_{i))$:

${\displaystyle M=cmmmc(m_{1},m_{2},...,m_{n})}$

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

Portal Matematică