Bonjour,

Tout est dans le titre, je ne comprends pas du tout le système de remonté via l'algo d'Euclide.

Merci.

Petit exemple :

PGCD(138 807 ; 52 089) = 291 :
138 807 = 52 089 × 2 + 34 629
52 089 = 34 629 × 1 + 17 460
34 629 = 17 460 × 1 + 17 169
17 460 = 17 169 × 1 + 291

On en déduit successivement, en commençant par la dernière égalité :

291 = 17 460 − 17 169 // Ici ça va
291 = 17 460 − (34 629 − 17 460) = 17 460 × 2 − 34 629 // Pourquoi il y a un 17460 en plus ?
291 = (52 089 − 34 629) × 2 − 34 629 = 52 089 × 2 − 34 629 × 3
291 = 52 089 × 2 − (138 807 − 52 089 × 2) × 3
= − 138 807 × 3 + 52 089 × 8 et donc (u,v) = (-3,8

> 291 = 17 460 − (34 629 − 17 460) = 17 460 × 2 − 34 629 // Pourquoi il y a un 17460 en plus ?

17 460 − (34 629 − 17 460) = 17 460 − 34 629 −(-17 460) = 17 460 − 34 629 + 17 460 = 2×17 460 − 34629.

Citation : totoxic21

PGCD(138 807 ; 52 089) = 291 :
138 807 = 52 089 × 2 + 34 629
52 089 = 34 629 × 1 + 17 460
34 629 = 17 460 × 1 + 17 169
17 460 = 17 169 × 1 + 291

A partir de là, il y a deux méthodes:

La galère qui fait 50 lignes... Qui consiste a remonter dans tes égalités.

Et l'astucieuse !!!

138 807 = 52 089 × 2 + 34 629
52 089 = 34 629 × 1 + 17 460
34 629 = 17 460 × 1 + 17 169
17 460 = 17 169 × 1 + 291

Peut se réécrire:

(1) 138 807 - 52 089 × 2 - 34 629 = 0
(2) 52 089 - 34 629 × 1 - 17 460 = 0
(3) 34 629 - 17 460 × 1 - 17 169 = 0
(4) 17 460 - 17 169 × 1 = 291

Dans (4), 17 169 est présent -1 fois, on multiplie donc la ligne (3) par -1 comme ça lorsque l'on additionnera -1*(3) et (4) les 17 169 s'annuleront.

17 460 apparaît 1 fois dans la ligne (3) multiplié par -1, de plus il est également 1 fois dans la ligne (4) il apparaît donc 2 fois. On multiplie donc la ligne (2) par 2 car lorsque l'on additionnera 2*(2)-1*(3)+(4) les 17 460 et les 17 169 s'annuleront

Dans la ligne (2) que l'on a multiplié par 2, 34 629 apparaît -2 fois De plus il apparaît -1 fois dans la ligne (3) multiplié par -1 Il apparaît donc au total -3 fois. On multiplie donc la ligne (1) par -3.

Ainsi en effectuant l'opération: -3*(1)+2*(2)-1*(3)+(4), on obtient:

-3*138 807 + 6*52 089+2*52 089 = 291
-3*138 807 + 8*52 089 = 291

Donc le couple (-3,8) est le couple recherché !

Bon là j'ai détaillé le raisonnement pour que tu puisses comprendre, mais normalement il faut être capable de pouvoir écrire les facteurs correspondant à chaque ligne dans la minute qui suis la fin de l'algorithme. Cette méthode réduit beaucoup les calculs, mais peut s'avérer être très casse gueule (c'est d'ailleurs pour ça que les profs évitent de l'enseigner...) si on ne fait pas suffisamment attention.

Bonjour,

Tout d'abord merci pour votre aide, alors bon je pense avoir compris un peu le principe mais j'ai essayé de mettre en application et je n'ai pas trouvé les bons résultats

PGCD(255,141)

255 = 141 x 1 + 114
141 = 114 x 1 + 27
114 = 27 x 4 + 6
27 = 6 x 4 + 3

Bézout : ( mon calcul)

3 = 27 - 6 x 4

3 = (114 - 27 x 4 -6)x -4 + 27 - 6x4

3 = (141 - 114 - 27)x 9 + 114 - 4 + 27 x 9
= 141 x 9 + 114 x -13

3 = (255 - 141 - 114)x -13 + 141 x 9 - 114x13
= 255x(-13) + 141x(22)

Je pense que je dois mal utiliser la méthode :S

Merci

Une fois que tu as ça:

255 = 141 x 1 + 114
141 = 114 x 1 + 27
114 = 27 x 4 + 6
27 = 6 x 4 + 3

Tu le réécris sous cette forme:

255 - 141 x 1 - 114 = 0
141 - 114 x 1 - 27 = 0
114 - 27 x 4 + 6 = 0
27 - 6 x 4 = 3

Ensuite sur ton papier tu traces un trait vertical à droite de ton système et à la droite de ce trait tu écris les multiplications pour chacune des lignes de tel sorte que lorsque tu les additionnes toutes ensembles, tout s'annule excepté les 2 termes dont tu as cherché le pgcd.

Tu dois obtenir ça:



Ainsi:

255x(-21)+141x21+141x17=-21x255+38x141=3

Alors j'ai fais ce que tu as dis et j'ai compris donc pour le 4 mais après c'est le 17 que je ne comprends pas, pourquoi pas 9 ? Car j'ai après calcul (pour l'avant dernière ligne ) :

114 x -4 + 27 x 9


Merci de ta patience par ailleurs

En multipliant l'avant dernière ligne par -4 tu multiplies ton nombre de 27 par -4 or tu en avais déjà -4, ça en fait donc 16, tu rajoutes le 27 de la ligne d'en dessous et tu en obtiens 17.

Pour le -21: Tu as multiplié par 17 la deuxieme donc tu as (-17) 114 de plus en multipliant la ligne d'en dessous par -4 tu est passé à (-4) 114, ça te fait donc -17-4=-21 pour la première ligne

Oui je viens juste de m'en apercevoir à force de voir trop compliqué on perd les choses simples, le -4 factorise toute la ligne et ça j'ai pas fait attention j'ai additionné le -4.

Big merci à toi

Après ça nécessite un certain entrainement, c'est pas parce que l'on est arrivé à le faire une fois qu'on y arrive tout le temps mais quand on a prit le coup ça devient très rapide. De plus quand il y a une erreur elle peut se repérer rapidement (des calculs de pgcd qui font plus de 5/6 lignes c'est assez rare).

Ah et aussi, si un jour tu étudies les pgcd sur les polynômes, je te déconseille vivement d'utiliser cette méthode car elle devient encore pire que casse gueule, et pour repérer là où il y a une erreur ça peut devenir vraiment compliqué... Enfin pour le moment je doute que tu en sois là.