Next:
Autres résultats utiles
Up:
No Title
Previous:
Complexité du algorithme d'Euclide
Résultats utiles
Théorème des restes chinois:
Si
sont des entiers supérieures à 2 deux-à-deux premiers entre eux, alors pour des entiers
le système des équations
admet une solution unique modulo
donnée par:
où
et
.
Exemple
Supposons:
.
On calcule
M
=1001,
,
,
Algorithme d'Euclide:
,
et
Par le théorème des restes chinois:
Par exemple, si on a le système:
La solution est:
sont des entiers supérieures à 2 deux-à-deux premiers
entre eux, alors pour des entiers 
le système des équations 
admet une solution unique modulo 
donnée par:
et 
.
.
, 
, 
, 
et 
