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{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}}$${\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}}$

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}}}$$x\equiv y{\pmod {n_{i}}}$ pentru orice $1\leq i\leq k$$1\leq i\leq k$, dacă și numai dacă $x\equiv y{\pmod {N}}$$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.\,\!$$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