Teorema chinezească a resturilor

Formularea originală a lui Sun-tzu: sistemul:$x\equiv 2{\pmod {3}}$ $x\equiv 3{\pmod {5}}$ $x\equiv 2{\pmod {7}}$ Are o infinitate de soluții $x=23+105k$, unde $k\in \mathbb {Z}$

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ț

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

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

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

Exemplu

Să considerăm sistemul:

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

Conform formulei $x=\sum _{k=1}^{n}{a_{k}X_{k}{X_{k}}_{m_{k}}^{-1}}$, soluția se va calcula drept: $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: $x=263+105k$.

Generalizare

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

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

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

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

Bibliografie

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