Teorema chinezească a resturilor

Teorema chinezească a resturilor este un rezultat 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, și apoi, în 1247, într-o altă carte a lui Qin Jiushao.

Enunț

Dacă n₁, n₂, …, n_k sunt întregi primi între ei doi câte doi, atunci, oricare ar fi întregii dați a₁,a₂, …, a_k, există un întreg x care este soluție a următorului sistem de congruențe:

$\begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align}$

Mai mult, toate soluțiile x ale acestui sistem sunt congruente modulo produsul N = n₁n₂…n_k.

Formulare alternativă și generalizare

Deci $x\equiv y \pmod{n_i}$ pentru orice $1\leq i \leq k$, dacă și numai dacă $x \equiv y \pmod{N}$.

Uneori, sistemul de congruențe poate fi rezolvat chiar dacă numerele n_i' nu sunt prime între ele două câte două. O soluție x există dacă și numai dacă:

$a_i \equiv a_j \pmod{cmmdc(n_i,n_j)} \qquad \forall i, j. \,\!$

Toate soluțiile x sunt, atunci, congruente modulo cel mai mic multiplu comun al numerelor n_i.

Bibliografie

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