Plus grand commun diviseur (pgcd)
Existence du pgcd
Soient \(a\) et \(b\) deux nombres entiers, qu'on suppose positifs dans tout ce paragraphe. Existe-t-il un plus grand commun diviseur de \(a\) et \(b ?\) La réponse est évidemment oui, puisqu'il suffit d'examiner les diviseurs de \(a,\) ceux de \(b\) 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 \(a\) et \(b\) deux entiers relatifs non nuls. On appelle plus grand diviseur commun à \(a\) et \(b\) le plus grand entier tel que \(d \mid a\) et \(d \mid b.\)
Remarque :
On note pgcd \((a,b)\) le plus grand entier tel que \(d \mid a\) et \(d \mid b.\) Il est évident que le plus grand diviseur commun est positif, puisque si un entier divise \(a\) et \(b,\) son opposé aussi. Il est aussi unique par définition même.
Propriété :
Soient deux entiers non nuls appartenant à \(\mathbb N.\) Si un entier positif \(d\) est tel que les deux propriétés suivantes soient vérifiées :
\(d \mid a\) et \(d \mid b\)
si \(c\) est un entier positif qui divise \(a\) et \(b,\) alors \(c \mid d\)
alors \(d\) est le plus grand commun diviseur de ces deux entiers, \(d = \textrm {pgcd} (a,b).\)
Démonstration :
D'après la propriété \((c \mid d \quad \textrm {et} \quad d \neq 0) \Rightarrow c \leq d,\) si un entier \(d\) vérifie les deux propriétés précédentes, il est plus grand que tous les diviseurs communs \(c\) de \(a\) et \(b\) et c'est le \(\textrm {pgcd} (a,b).\) On cherche donc un plus grand diviseur commun \(d\) au sens tout autre diviseur commun de \(a\) et \(b\) est un diviseur de \(d,\) notion qui entraîne que \(d\) 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 \(\delta\) est un diviseur commun à \(a\) et \(b,\) c'est aussi un diviseur commun à \(b\) et \(r,\) \(r\) étant le reste de la division de \(a\) par \(b.\)
Réciproquement un diviseur commun à \(b\) et \(r\) est un diviseur commun à \(a\) et \(b.\) Or le couple \((b, r)\) est un couple d'entiers plus petits que ceux du couple initial. On peut recommencer en faisant la division de \(b\) par \(r.\)
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 \(a\) = 95991 et \(b\) = 13083.
95991 = 13083 × 7 + 4410 soit \(a = 7b + r_1\) Les diviseurs communs à 95991 et 13083 sont ceux de 13083 et 4410.
13083 = 4410 × 2 + 4263 soit \(b = 2r_1 + r_2\) Les diviseurs communs à 13083 et 4410 sont ceux de 4410 et 4263.
4410 =4263 + 147 soit \(r_1 = r_2 + r_3\) Les diviseurs communs à 4410 et 4263 sont ceux de 4263 et 147.
4263 = 147 × 29 + 0 soit \(r_2 = 29 r_3\) Les diviseurs communs à 4263 et 147 sont les diviseurs de 147.
\(147 = \textrm {pgcd} (95991, 13083)\)
Démonstration : Algorithme d'Euclide
Soient \(a\) et \(b\) deux entiers positifs. Supposons que \(a\) est le plus grand, \(a \geq b,\) et divisons \(a\) par \(b : a = bq_1 + r_1\) avec \(0 \leq r1 < b.\)
Tout diviseur commun à \(a\) et \(b\) est un diviseur commun à \(b\) et \(r_1\) et réciproquement.
Donc \(\textrm {pgcd} (a,b) = \textrm {pgcd} (b,r_1).\)
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 \(r_k = 0.\)
\(\begin{array}{ccccccc}b&=&r_1 q_2 + r_2&\quad \textrm {et} \quad&0&\leq&r_2 < r_1\\r_1&=&r_2 q_3 + r_3&\quad \textrm {et} \quad&0&\leq&r_3 < r_2\\r_{k-3}&=&r_{k-2} q_{k-1} + r_{k-1}&\quad \textrm {et} \quad&0&\leq&r_{k-1} < r_{k-2}\\r_{k-2}&=&k_-1 q_k\end{array}\)
Donc \(r_{k-1}\) divise \(r_{k-2}\) et \(\textrm {pgcd} (r_{k-2}, r_{k-1}) = r_{k-1}\) et de proche en proche \(r_{k-1}=\textrm {pgcd} (a,b).\)
Cet algorithme est une démonstration d'existence du pgcd. Il permet aussi de montrer que tout diviseur commun à \(a\) et \(b\) est un diviseur de \(d.\) Comme nous l'avons vu sur l'exemple, cet algorithme permet de déterminer successivement chaque reste comme \(na + mb\) avec \(n\) et \(m\) entiers. Nous allons donc nous intéresser aux entiers qui peuvent s'écrire sous la forme \(ax + by.\)