Forum de mathématiques - Bibm@th.net

Etoiles

Membre

Inscription : 27-12-2008

Messages : 4

Theoreme des restes chinois [Résolu]

Bonjour :)
svp  j essaie de comprendre la theorie des restes chinois en utilisant l 'explication donné par le bibmath  je cite " 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.  "

je n 'arrive pas a calculer le yi=Mi-1

x=3 mod 17.
x=4 mod 11.
x=5 mod 6.
On applique le théorème chinois : on a M=17×11×6=1122, M1=66, M2=102, M3=187. L'inversion de chaque Mi (par l'algorithme d'Euclide) donne y1=8, y2=4, y3=1.
COMMENT trouves t -on les Y  SOIT y1=8, y2=4, y3=1

MERCI BCP

EXCELLENTE journée et bonnes fetes

Golgup

Membre actif

Inscription : 09-07-2008

Messages : 574

Re : Theoreme des restes chinois [Résolu]

Bijour,

Les Yi sont tels que YiMi=1(mod mi). Donc le but est de trouver l'inverse de Mi mod mi, d'ou l'algorithme d'Euclide (etendu)..!

Ont sait que a a un inverse mod n seulement si pgcd(a;n)=1
Et on sait ussi que si a et n son 1er entre eux, il existe u et v avec ua+vn=1
donc que ua mod n =1

Dans l'exemple, l'inverse de 66 mod 17 est 8, car 8x66-31x17=1. Donc 66*8=1mod17. Avec ici, u=8 et v=-31..etc pour les autres

@+

Etoiles

Membre

Inscription : 27-12-2008

Messages : 4

Re : Theoreme des restes chinois [Résolu]

Bonjour Golgup
merci de ta réponse , je suis autoditacte ...

donc si j 'ai bien suivi pour Y2
102 U - 11V  = 1

Mais comment trouver ces valeurs
Essayer des nombres  qui verifie cette egalité ?

Merci de ta reponse agreable journée :)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Theoreme des restes chinois [Résolu]

Bonjour,

La réponse à ta question est : Identité de Bachet-Bezout, appelée couramment Théorème de Bezout (Classe de Term S, Enseignement de spécialité).
Il te faut trouver une solution particulière simple, ici U_0=4 et V_0 = 37, puis tu en déduis toutes les solutions :
[tex]U_k=4-11*k\;\;\text{et}\;\;V_k=37-102*k\text{,}\;\forall\;k \in\mathbb{Z}[/tex]

Voir aussi : http://www.bibmath.net/forums/viewtopic.php?id=2283

@+

[EDIT]
Un remords de conscience...
Pour trouver 4 et 37, soit tu programmes (en Python par exemple) 4/5 lignes et tu as ta réponse, soit tu procèdes ainsi par divisions successives jusqu'à un reste de 1 (algorithme d'Euclide)
102 = 11 * 9 + 3
  11 =  3 * 3 + 2
    3 =  2 * 1 + 1
Et maintenant, on repart en arrière :
1 = 3 - 2 * 1
1 = 3 - (11 - 3 *3) * 1
On développe :
1 = 3 - 11 + 3 *3
C'est à dire :
1 = 3 + 3 *3 - 11  (on factorise)
1 = 3 * 4 - 11  (on remplace le 3)
1 = (102 - 11*9) * 4 - 11
1 = 102 * 4 - 11 *9 * 4 - 11
1 = 102 * 4 - 11 * 36 - 11 (on factorise)
1 = 102 * 4 - 11 * 37 = 102 * 4 + (-11) * 37

Dernière modification par yoshi (29-12-2008 12:30:08)

Golgup

Membre actif

Inscription : 09-07-2008

Messages : 574

Re : Theoreme des restes chinois [Résolu]

Re,

Oui mais il faut trouver 'la solution particulierement simple'. Et 1 solution suffit.

comment trouver u et v:

On pose [tex]{U}_{0}=1\,[/tex] ,  [tex]{U}_{1}=0[/tex]   ,  [tex]{V}_{0}=0[/tex]  ,  [tex]{V}_{1}=1[/tex].
[tex]{Q}_{k}[/tex]=La suite des quotients calculés.
[tex]{R}_{k}[/tex]=La suite des restes calculés.

Le but est de construir deux suites [tex]{U}_{k}[/tex]  et  [tex]{V}_{k}[/tex] tres facilement de longeur du nombre d'etapes pour trouver le pgcd de a et b, +1.

Avec [tex]{U}_{k+1}={Q}_{k}{U}_{k}+{U}_{k-1}[/tex]
et [tex]{V}_{k+1}={Q}_{k}{V}_{k}+{V}_{k-1}[/tex]

Puis on en deduira [tex]U={\left(-1\right)}^{n}{U}_{n}[/tex]
et [tex]V={\left(-1\right)}^{n+1}{V}_{n}[/tex]

Avec n=Le nbre d'etapes pour trouver le pgcd.

Dans ton exemple, (avec [tex]{Y}_{1}[/tex]);

pgcd(17,66)=1, trouvé en 4 etapes, donc k= 0,1,2,3,4,5. et n=4.

k=    0 ,  1 ,  2 ,  3 ,  4 ,  5

[tex]{R}_{k}[/tex]=66 , 17 , 15 , 2 , 1 , 0

[tex]{Q}_{k}[/tex]=       3     1    7   2

[tex]{U}_{k}[/tex]=1  ,  0  ,   1 , 1  , 8 , 16

[tex]{V}_{k}[/tex]=0     1   ,  3 , 4 , 31 , 66

On a donc [tex]U={\left(-1\right)}^{4}{U}_{1}={\left(-1\right)}^{4}8=8[/tex]
et [tex]V={\left(-1\right)}^{4+1}{V}_{1}={\left(-1\right)}^{5}31=-31[/tex]

Donc U=8 et V=-31

si tu comprends po! , di!

++
[edit]
A zut, m'sieur Yoshi a posté avant, tu choisi..

Dernière modification par Golgup (29-12-2008 13:30:10)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Theoreme des restes chinois [Résolu]

Salut,

Pour répondre à l'EDIT de Golgup, la méthode que j'ai indiquée est celle qui figure dans les bouquins de TS avec application au Tableur ensuite.

@+

Etoiles

Membre

Inscription : 27-12-2008

Messages : 4

Re : Theoreme des restes chinois [Résolu]

bonjour Yoshi
apres avoir étudier le theoreme d 'euclid et eucluid extendu ; J ai compris  la premiere partie mais je comprends pas comment tu fais pour revenir en arriere
je comprends le 3 = 2x1 +1 qui devient  le 3 -2X1= 1
mais aprés je comprend pas le procedé ni comment dans l etape on remplace le 3
ET dans l avant derniere etape tu factorises 4 ou 11
merci de ton aide

excellente journée

Bonjour,

La réponse à ta question est : Identité de Bachet-Bezout, appelée couramment Théorème de Bezout (Classe de Term S, Enseignement de spécialité).
Il te faut trouver une solution particulière simple, ici U_0=4 et V_0 = 37, puis tu en déduis toutes les solutions :
[tex]U_k=4-11*k\;\;\text{et}\;\;V_k=37-102*k\text{,}\;\forall\;k \in\mathbb{Z}[/tex]

Voir aussi : http://www.bibmath.net/forums/viewtopic.php?id=2283

@+

[EDIT]
Un remords de conscience...
Pour trouver 4 et 37, soit tu programmes (en Python par exemple) 4/5 lignes et tu as ta réponse, soit tu procèdes ainsi par divisions successives jusqu'à un reste de 1 (algorithme d'Euclide)
102 = 11 * 9 + 3
  11 =  3 * 3 + 2
    3 =  2 * 1 + 1
Et maintenant, on repart en arrière :
1 = 3 - 2 * 1
1 = 3 - (11 - 3 *3) * 1
On développe :
1 = 3 - 11 + 3 *3
C'est à dire :
1 = 3 + 3 *3 - 11  (on factorise)
1 = 3 * 4 - 11  (on remplace le 3)
1 = (102 - 11*9) * 4 - 11
1 = 102 * 4 - 11 *9 * 4 - 11
1 = 102 * 4 - 11 * 36 - 11 (on factorise)
1 = 102 * 4 - 11 * 37 = 102 * 4 + (-11) * 37

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Theoreme des restes chinois [Résolu]

Bonjour,

Ah, bin dis donc, ça ne devait pas avoir un caractère d'urgence folle...

Donc voilà, je reprends et je détaille davantage :
102 = 11 * 9 + 3
  11 =  3 * 3 + 2
    3 =  2 * 1 + 1
Et maintenant, on repart en arrière :
1 = 3 - 2 * 1
1 = 3 - (11 - 3 *3) * 1 --> La partie en gras correspond à la ligne 11 = 3*3 +2
On développe la partie (11 - 3 *3) * 1 en distribuant le 1 :
1 = 3 - 11 + 3 *3
C'est à dire :
1 = 3 + 3 *3 - 11   Là, j'ai semblé passé le 3 * 3 devant le -11 pour que la factorisation apparaisse plus clairement
On factorise alors la partie 3 + 3 * 3 en pensant bien que 3 c'est 3 * 1 : 3 * 1 + 3 * 3 = 3 *(1 + 3)
1 = 3 * 4 - 11 
On remplace maintenant  le 3 en l'extrayant de 102 = 11 * 9 + 3 qui donne 3 = 102 - 11 * 9
1 = (102 - 11*9) * 4 - 11
On développe alors en distribuant le 4 sur 102 et sur -11 * 9
1 = 102 * 4 - 11 *9 * 4 - 11
9 * 4 = 36, je remplace, puis je mets 11 en facteur
1 = 102 * 4 - 11 * 36 - 11
Là encore, je pense bien que 11 = 11 * 1 :
1 = 102 * 4 -11 * (36 + 1)
D'où
1 = 102 * 4 - 11 * 37 = 102 * 4 + (-11) * 37

C'est bon ?

@+

PS : il ne faut pas perdre de vue l'énoncé qui contient les nombres 102 et 11, il faut bien que je les fasse apparaître mais qu'après je ne les "dilue" pas

Etoiles

Membre

Inscription : 27-12-2008

Messages : 4

Re : Theoreme des restes chinois [Résolu]

Bonjour Merci bcp :) C 'est plus clair mais tout nouveau pour moi je vais etudier ca et  pratiquer cette approche .et essayer avec d 'autre examples  merci encore  ... excellent  week end :)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Theoreme des restes chinois [Résolu]

Salut,

Voici un autre exemple, brut de décoffrage, sans explication mais assez détaillé.
Trouver x et y tels que 99x + 53y = 1
Recherche d'une solution simple.
99 = 53 * 1 + 46
56 = 46 * 1 +  7
46 =   7 * 6 +  4
  7 =   4 * 1 + 3
  4 = 3 x 1 + 1

D'où  :   1 =   4 - 3 * 1
             1 =   4 - (7 -  4 * 1) * 1
             1 =   4 - 7 * 1 + 4 * 1
             1 =   4 * 2 - 7 * 1
             1 =  (46 - 7 * 6) * 2 - 7 * 1
             1 =   46 * 2 - 7 * 6 * 2 - 7 * 1
             1 =   46 * 2  - 7 * 12 - 7 * 1
             1 =   46 * 2 - 7 * 13
             1 =   46 * 2 - (53 - 46 * 1) * 13
             1 =   46 * 2 - 53 * 13 + 46 * 13
             1 =   46 * 2 + 46 * 13 - 53 * 13
             1 =   46 * 15 - 53 * 13
             1 = (99 -53 * 1) * 15 - 53 * 13
             1 =  99 * 15 - 53 * 15 - 53 * 13
             1 =  99 * 15 - 53 * 28
             1 =  99 * 15 + 53 * (-28)

Solution simple : (x ; y) = (15 ; -28)

@+