Answered

quelles sont les etapes pour calculer le pgcd avec la methode euclidienne ? 

Merci .

Sagot :

Nous connaissons deux méthodes  permettant de calculer le PGCD de deux nombres entiers (positifs) : 1)  La méthode des soustractions successives ; 2) la méthode des divisions successives dite « algorithme d’Euclide ». Dans cette activité, nous allons mettre en oeuvre ces deux méthodes et ainsi constater qu’elle n’ont pas la même efficacité.  Avec la méthode des soustractions successives a)       Taper la feuille de calcul suivante ; adapter la largeur des colonnes.   A B C D 1 Calcul du PGCD par les soustractions successives 2 Nb. d’étapes a b a – b 3 1 3356 1528   4         ……… …………… …………… …………….. …………….                                
      b)       Dans la cellule A3 taper 1 ; dans B3 taper le plus grand des deux nombres et dans C3 le plus petit ; dans D3, taper « =B3-C3) ». c)        Dans A4 taper « =A3+1 » ; dans B4 taper « =max(C3 ; D3) » ; dans C4 taper « =min(C3 ; D3 ) » ; recopier D3 en D4. d)       Après avoir sélectionner la ligne 4, recopier vers le bas toutes les cellules jusqu’à faire apparaître le PGCD de 3356 et 1528. e)        Recopier dans le tableau ci-dessus les quatre dernières étapes. Quel est le PGCD de 3356 et 1528 ? Combien d’étapes ont été nécessaires pour l’obtenir ?  Avec l’algorithme d’Euclide a)       Taper la feuille de calcul suivante ; adapter la largeur des colonnes.    F G H I 1 Calcul du PGCD par l’algorithme d’Euclide 2 Nb. D’étapes a b reste 3 1 3356 1528   4         5         6         7         8         b)       Dans la cellule I3 taper « =mod(G3 ; H3) » ; ce calcul permet de déterminer le reste de la division euclidienne de 3356 par 1528. c)        Procéder comme précédemment pour que la cellule F4 indique le nombre d’étapes, que G4 reçoive le plus grand des deux nombres en H3 et I3, H4 le plus petit et que I4 soit le reste dans la division euclidienne de G4 par H4. d)       Recopier dans le tableau ci-dessus toutes les étapes. Quelle est la méthode la plus rapide ?  Conclusion : On constate que la méthode la plus efficace est l’algorithme d’Euclide. Utiliser cet algorithme (et le tableau précédent) pour déterminer le PGCD des nombres suivants : a)       PGCD(2277 ; 1449)= ……….. ;           b)   PGCD(74925 ; 6882)= ………………….