Mathématiques
Précédent
Suivant
Plus grand commun diviseur (pgcd)
Existence du pgcd

Soient et deux nombres entiers, qu'on suppose positifs dans tout ce paragraphe. Existe-t-il un plus grand commun diviseur de et La réponse est évidemment oui, puisqu'il suffit d'examiner les diviseurs de ceux de qui sont en nombre fini, chercher les diviseurs communs et prendre le plus grand.

Sur un exemple, nous verrons les limites de cette méthode : cherchons le pgcd de 24 et 60. Diviseurs de 24 : 1, 2, 3, 4, 6, 8, 12, 24 et leurs opposés. Diviseurs de 60 : 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 et leurs opposés. Diviseurs communs de 24 et 60 : 1, 2, 3, 4, 6, 12 et leurs opposés. Le plus grand de ces diviseurs est 12.

L'écriture des diviseurs n'est possible que pour des petits nombres, et encore faut-il une méthode systématique pour ne pas en oublier. Cette méthode ne nous apprend pas grand-chose. Dans ce chapitre nous allons élaborer une méthode de détermination du plus grand commun diviseur de deux entiers.

Définition

Soient et deux entiers relatifs non nuls. On appelle plus grand diviseur commun à et le plus grand entier tel que et

Remarque

On note pgcd le plus grand entier tel que et Il est évident que le plus grand diviseur commun est positif, puisque si un entier divise et son opposé aussi. Il est aussi unique par définition même.

Propriété

Soient deux entiers non nuls appartenant à Si un entier positif est tel que les deux propriétés suivantes soient vérifiées :

  • et

  • si est un entier positif qui divise et alors

alors est le plus grand commun diviseur de ces deux entiers,

Démonstration

D'après la propriété si un entier vérifie les deux propriétés précédentes, il est plus grand que tous les diviseurs communs de et et c'est le On cherche donc un plus grand diviseur commun au sens tout autre diviseur commun de et est un diviseur de notion qui entraîne que est aussi plus grand, (au sens de la relation d'ordre), que tout diviseur commun.

Détermination pratique du pgcd

La plus ancienne méthode de détermination du pgcd de deux entiers, l'algorithme d'Euclide, date de l'Antiquité grecque (environ trois siècles avant notre ère), et fournit une méthode pratique de détermination du pgcd. L'algorithme d'Euclide repose sur la division deux entiers, et sur la remarque suivante :

Si est un diviseur commun à et c'est aussi un diviseur commun à et étant le reste de la division de par

Réciproquement un diviseur commun à et est un diviseur commun à et Or le couple est un couple d'entiers plus petits que ceux du couple initial. On peut recommencer en faisant la division de par

Exemple : Détermination pratique du pgcd

Sur l'exemple précédent :

60 = 24 × 2 + 12 et 24 = 2 × 12, donc 12 est le pgcd de 60 et 24.

Deuxième exemple qui sert de guide pour la démonstration générale.

Chercher le pgcd de = 95991 et = 13083.

95991 = 13083 × 7 + 4410 soit Les diviseurs communs à 95991 et 13083 sont ceux de 13083 et 4410.

13083 = 4410 × 2 + 4263 soit Les diviseurs communs à 13083 et 4410 sont ceux de 4410 et 4263.

4410 =4263 + 147 soit Les diviseurs communs à 4410 et 4263 sont ceux de 4263 et 147.

4263 = 147 × 29 + 0 soit Les diviseurs communs à 4263 et 147 sont les diviseurs de 147.

Démonstration : Algorithme d'Euclide

Soient et deux entiers positifs. Supposons que est le plus grand, et divisons par avec

Tout diviseur commun à et est un diviseur commun à et et réciproquement.

Donc

On itère le procédé et l'on sait que la suite des restes obtenue est une suite d'entiers strictement décroissante. Donc à un certain stade

Donc divise et et de proche en proche

Cet algorithme est une démonstration d'existence du pgcd. Il permet aussi de montrer que tout diviseur commun à et est un diviseur de Comme nous l'avons vu sur l'exemple, cet algorithme permet de déterminer successivement chaque reste comme avec et entiers. Nous allons donc nous intéresser aux entiers qui peuvent s'écrire sous la forme

Légende :
Apprendre
S'évaluer
S'exercer
Observer
Simuler
Réalisé avec Scenari (nouvelle fenêtre)