Teorema chinezească a resturilor

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.