Théorême des restes chinois

[invite56460777]

Bonjour,

J'ai la définition suivante du théorêmes des restes chinois:

Théorème : Prenons m1, ..., mn des entiers supérieurs à 2 deux à deux premiers entre eux, et a1,...,an des entiers. Le système d'équations :
x=a1 mod m1
...
x=an mod mn
admet une unique solution modulo M=m1×...×mn donnée par la formule :
x=a1M1y1+...+anMnyn mod M
où Mi=M/mi, et yi=Mi-1 mod mi pour i compris entre 1 et n.

Maintenant, j'essaie de l'appliquer pour résoudre un système de congruences:

x =^ 1 mod 3
x =^ 2 mod 4
x =^ 3 mod 5
x =^ 4 mod 7
3, 4, 5 et 7 sont bien deux à deux premiers
On a une solution x = (1*M_1*y_1)+(2*M_2*y_2)+ (3*M_3*y_3)+(4*M_4*y_4) mod 420
Maintenant je cherche à déterminer M_1, M_2, M_3, M_4
En principe M_1 = M/m_1 = 420/m_1.

m_1 est-il égal à 3 ? m_2 = 4? m_3 = 5? m_4 = 7?
Si tel est le cas, faudrait-il appliquer l'algorithme d'Euclide à M_1 et 3??? (M_1 et 3 sont alors premiers entre eux)

Cela me ferait plaisir d'avoir plus d'explications...J'ai l'impression d'avoir mal compris le principe de ce théorême.
Merci d'avance,
-----

[Antikhippe]

Salut,

Est-ce-que t'as le Soulami, par hasard ?

Parce que là-dedans, c'est très bien expliqué...

[invite56460777]

Non, je ne l'ai pas. Pourrais-tu éventuellement me scanner la page en question ou m'expliquer rapidement comment procéder pour que tout le monde en profite?

[Antikhippe]

Aïe... Le problème, c'est que mon scanner est en panne et de toutes façons, j'ai prété le livre à un ami...

Je ne me souviens plus de grand chose sur ce théorème...

Je vais voir ce que je peux faire.

[A voir en vidéo sur Futura]

[Antikhippe]

Voici un exemple :

Soit le système :
x 0 [3]
x 1 [5]
x 7 [8]

Toutes les solutions de ce système sont congrues à 111 modulo 120.

[GuYem]

Dans le théroème des restes chinois, les coefficients cherchés sont souvent donnés par la relation de Bezout, écrite autant de fois que nécessaire entre tous les couples de nombres premiers entre eux que l'on te donne.
Si tu veux les calculer effectivement, il faudra faire du Euclide en effet; comme à chaque fois que tu veux trouver les fameux coeff de Bezout.

[invitea77054e9]

Le thorème chinois peut s'énoncer d'une autre manière, peut-être plus claire (quoique !).

Notons Z/nZ l'ensemble des classes d'équivalence pour la relation de congruence modulo n.

Si a et b sont premiers entre eux, alors il existe un isomorphisme f: Z/abZ->Z/aZ X Z/bZ (X représente le produit cartésien de deux ensembles).

Plus génèralement, soient a1, a2, ..., an n entiers premiers entre eux deux à deux, alors il existe un isomorphisme f: Z/aZ-> Z/a1Z X Z/a2Z X .... XZ/anZ , ou a=a1*a2*...*an .

[invite56460777]

Merci pour les explications complémentaires. Finalement, avec de l'ordre, de la méthode et du calme, ca ne coupait pas la queue aux grenouilles, comme on dit dans ma famille!