Calculer le PGCD

 Révision du programme de Maths 3ieme année Collège



Calculer le PGCD (Plus Grand Commun Diviseur) de deux nombres entiers :

Le PGCD de deux entiers est le plus grand nombre entier qui divise à la fois les deux entiers sans laisser de reste. Par exemple, le PGCD de 12 et 18 est 6, car 6 est le plus grand nombre qui divise à la fois 12 et 18.

Méthodes pour calculer le PGCD :

  1. Méthode par liste des diviseurs :

    Cette méthode consiste à lister tous les diviseurs des deux nombres et à choisir le plus grand diviseur commun.

    Exemple :
    Trouver le PGCD de 24 et 36 :

    • Diviseurs de 24 : 1, 2, 3, 4, 6, 8, 12, 24

    • Diviseurs de 36 : 1, 2, 3, 4, 6, 9, 12, 18, 36

    Le plus grand diviseur commun est 12. Donc, le PGCD de 24 et 36 est 12.

  2. Méthode de l'algorithme d'Euclide (plus rapide) :

    L'algorithme d'Euclide repose sur la division successive. Il consiste à remplacer le plus grand des deux nombres par le reste de la division de ces deux nombres. On répète ce processus jusqu’à ce qu'on obtienne un reste nul. Le dernier diviseur non nul est le PGCD.

    Étapes de l'algorithme d'Euclide :

    • Diviser le plus grand nombre par le plus petit.

    • Remplacer le plus grand nombre par le reste de cette division.

    • Répéter l'opération jusqu'à ce que le reste soit 0.

    • Le PGCD est le dernier diviseur non nul.

    Exemple :
    Trouver le PGCD de 24 et 36 en utilisant l'algorithme d'Euclide :

    1. Diviser 36 par 24 :
      36÷24=136 \div 24 = 1 reste 1212

    2. Diviser 24 par 12 :
      24÷12=224 \div 12 = 2  reste 00

    Le reste est 0, donc le PGCD est 12.

Résumé des étapes :

  • Méthode par liste de diviseurs : Liste les diviseurs des deux nombres, choisis le plus grand diviseur commun.

  • Méthode de l'algorithme d'Euclide : Divise le plus grand nombre par le plus petit, remplace le plus grand nombre par le reste, et répète jusqu'à obtenir un reste nul. Le dernier diviseur non nul est le PGCD.

Applications du PGCD :

Le calcul du PGCD est utilisé dans de nombreux domaines, notamment en arithmétique, en simplification de fractions (pour réduire une fraction à sa forme la plus simple), et en cryptographie (comme dans le cas des clés RSA).

Exercice de pratique :

Trouve le PGCD de 48 et 180 en utilisant l'algorithme d'Euclide :

  1. Diviser 180 par 48.

  2. Diviser 48 par le reste précédent, etc.

Teste cette méthode et découvre la réponse ! 😊


Téléchargé la série 

Commentaires