L'appli sur Google Play

EXOMATH, PGCD

Acceder directement à la leçon
exercices intéractifs

PGCD, algorithme d'Euclide.

Le PGCD (Plus Grand Diviseur Commun) de plusieurs nombres est le plus grand nombre entier possible qui divise tous ces nombres. Par exemple le PGCD de 12,15,18 est 3 car 3 divise 12, 15 et 16 et il n'y a pas d'autre nombre plus grand que 3 qui divise 12, 15 et 18.

 

On peut trouver le PGCD de plusieurs entiers en décomposant ces nombres en produit de nombres premiers (2,3,5,7,11,13,17,19,23,29,31,37...) et en relevant les nombres qui se trouvent dans tous les produits.

Par exemple :

60 = 2 x 2 x 3 x 5

54 = 2 x 3 x 3 x 3

24 = 2 x 2 x 2 x 3

On retrouve un 2 et un 3 dans tous les produits, le PGCD est donc 2 x 3 = 6 !!! 

 

Deux nombres sont dits premiers entre eux si leur PGCD vaut 1 c'est à dire qu'ils n'ont aucun diviseur commun autre que 1. 

Par exemple, 15 et 22 sont premiers entre eux puisque leur seul diviseur commun est 1. (15 est dans la table de 1,3,5,15 il n'y a que 1 dans cette liste qui divise 22). Il ne faut pas confondre "nombre premier" et "nombres premiers entre eux". Ici, 15 et 22 ne sont pas des nombres premiers. Pourtant ils sont premiers entre eux. Des nombres premiers distincts sont forcément premiers entre eux.

 

L'algorithme d'Euclide permet de trouver le PGCD de deux nombres. Il s'agit de divisions successives et le pgcd est le dernier reste non nul :

 

 

 

L'exercice

Cherchez le pgcd par la méthode de votre choix puis répondez.

Le pgcd de et vaut

Les nombres et sont premiers entre eux :

Oui                 Non