Plus grand commun diviseur et plus petit commun multiple

Le plus grand commun diviseur et le plus petit commun multiple

Dans la leçon sur la divisibilité et la division euclidienne, on a étudié la relation $d \mid a$ entre deux entiers naturels. Lorsqu’on considère deux nombres à la fois, ce qui intéresse, ce sont les diviseurs qu’ils ont en commun et les multiples qu’ils partagent. Tout couple d’entiers naturels $a$ et $b$ a au moins un diviseur commun, à savoir $1$, et au plus un nombre fini d’entre eux, parce qu’aucun diviseur de $a$ ne dépasse $a$ ; il a, de plus, une infinité de multiples communs, parmi lesquels le produit $ab$. S’il en est ainsi, la définition suivante a un sens.

Définition (plus grand commun diviseur et plus petit commun multiple). Le plus grand commun diviseur de deux entiers naturels $a$ et $b$, que l’on note $\operatorname{pgcd}(a, b)$, est le plus grand entier naturel qui les divise tous les deux. Le plus petit commun multiple, que l’on note $\operatorname{ppcm}(a, b)$, est le plus petit entier naturel qui est multiple de chacun d’eux.

Le second est le plus petit élément d’un ensemble non vide d’entiers naturels, qui existe d’après le principe du bon ordre. Le premier est le plus grand élément de l’ensemble des diviseurs communs, qui n’est pas vide et qui est majoré par $a$ ; qu’un ensemble non vide et majoré d’entiers naturels ait un plus grand élément découle aussi du bon ordre : l’ensemble de ses majorants n’est pas vide et a un plus petit élément $M$, et $M$ appartient à l’ensemble, car sinon tout élément serait strictement inférieur à $M$ et, comme il n’y a pas d’entier naturel entre $M - 1$ et $M$, inférieur ou égal à $M - 1$, qui serait un majorant strictement inférieur à $M$ (si $M = 1$, l’ensemble est $\{1\}$ et contient $M$). Par exemple, les diviseurs communs de $12$ et $18$ sont $1$, $2$, $3$ et $6$, et leurs multiples communs sont $36$, $72$, $108$, et ainsi de suite :

De la définition découlent immédiatement quelques cas particuliers : $\operatorname{pgcd}(a, 1) = 1$ et $\operatorname{ppcm}(a, 1) = a$ ; $\operatorname{pgcd}(a, a) = \operatorname{ppcm}(a, a) = a$ ; et, si $a$ divise $b$, alors $\operatorname{pgcd}(a, b) = a$ et $\operatorname{ppcm}(a, b) = b$. Les deux opérations sont, de plus, symétriques : l’ordre des nombres ne change pas le résultat.

Calcul au moyen de la décomposition en facteurs premiers

D’après le théorème fondamental de l’arithmétique, tout entier naturel strictement supérieur à $1$ se décompose de manière unique en facteurs premiers. Il convient d’écrire $a$ et $b$ avec les mêmes nombres premiers $p_1, \ldots, p_k$, en admettant des exposants nuls pour les nombres premiers qui n’apparaissent que dans l’un d’eux :

Un entier naturel $d$ divise $a$ exactement lorsque sa décomposition ne contient pas d’autres nombres premiers que ceux de $a$, chacun avec un exposant inférieur ou égal à celui qu’il a dans $a$. Il s’ensuit que $d$ divise à la fois $a$ et $b$ lorsque l’exposant de chaque nombre premier dans $d$ ne dépasse aucun des deux exposants ; le plus grand diviseur commun s’obtient donc en prenant pour chaque nombre premier le plus petit des deux exposants. De même, $m$ est un multiple commun lorsque l’exposant de chaque nombre premier dans $m$ atteint les deux, et le plus petit multiple commun prend pour chaque nombre premier le plus grand des deux exposants. Par exemple :

La méthode est claire, mais elle suppose de savoir factoriser, et factoriser de grands nombres est très coûteux : on ne connaît aucun procédé rapide pour le faire. L’algorithme de la section suivante calcule le plus grand commun diviseur sans factoriser, uniquement par des divisions.