Teorema chinezească a resturilor

Formularea originală a lui Sun-tzu: sistemul:$x\equiv 2(\mathrm{mod}3)$ $x\equiv 3(\mathrm{mod}5)$ $x\equiv 2(\mathrm{mod}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 Sunzi în Sunzi Suanjing, 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{array}{cc}x& \equiv a_1(\mathrm{mod}{m}_1)\\ x& \equiv a_2(\mathrm{mod}{m}_2)\\ & ⋮\\ x& \equiv a_k(\mathrm{mod}{m}_k)\end{array}$

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}_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 $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\ne 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{array}{cc}x& \equiv 3(\mathrm{mod}5)\\ x& \equiv 4(\mathrm{mod}7)\\ x& \equiv 2(\mathrm{mod}3)\end{array}$

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(\mathrm{mod}{m}_i)$, unde $1\le i\le n$ este validă dacă și numai dacă $x\equiv y(\mathrm{mod}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(\mathrm{mod}cmmdc(m_i,m_j))\mathrm{\forall }1\le i,j\le 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

• Format:Citat carte