Teorema chinezească a resturilor
De la Wikipedia, enciclopedia liberă
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.
Cuprins |
[modifică] Enunţ
Dacă n1, n2, …, nk sunt întregi primi între ei doi câte doi, atunci, oricare ar fi întregii daţi a1,a2, …, ak, există un întreg x care este soluţie a următorului sistem de congruenţe[1]:
Mai mult, toate soluţiile x ale acestui sistem sunt congruente modulo produsul N = n1n2…nk.
[modifică] Formulare alternativă şi generalizare
Deci
pentru orice
, dacă şi numai dacă
.
Uneori, sistemul de congruenţe poate fi rezolvat chiar dacă numerele ni' nu sunt prime între ele două câte două. O soluţie x există dacă şi numai dacă:
Toate soluţiile x sunt, atunci, congruente modulo cel mai mic multiplu comun al numerelor ni.
[modifică] Note
- ^ Menezes, p. 68
[modifică] Bibliografie
- Alfred Menezes. Handbook of Applied Cryptography, Paul van Oorschot, Scott Vanstone.



