PGCD et PPCM

Les deux théorèmes qui se suivent sont agréablement parallèles ; il est donc amusant de constater que leurs preuves sont plus différentes qu'on ne pourrait s'y attendre. Il est possible de les déduire l'un de l'autre, mais il est instructif de les prouver très séparément. Vous verrez donc plusieurs preuves de l'un comme de l'autre.

Théorème 3   Soit $a\geqslant 1$ et $b\geqslant 1$ deux entiers. Alors il existe un unique entier $m\geqslant 1$ tel que pour tout entier $c\geqslant 1$,

$c$ est un multiple de $a$ et de $b$ si et seulement si $c$ est un multiple de $m$.

Théorème 4   Soit $a\geqslant 1$ et $b\geqslant 1$ deux entiers. Alors il existe un unique entier $d\geqslant 1$ tel que pour tout entier $c\geqslant 1$,

$c$ divise $a$ et $b$ si et seulement si $c$ divise $d$.

Ces théorèmes sont vendus avec deux compléments, le premier occasionnellement utile, le second totalement fondamental.

Complément 1 Pour tous $a$ et $b$, $md=ab$.

Complément 2 (Identité de Bézout)

Pour tous $a$ et $b$, il existe deux entiers (relatifs) $s$ et $t$ tels que $d=sa+tb$.

Et tant qu'on y est avant de passer aux démonstrations :

Définition 3   Le plus petit multiple commun de deux entiers $a$ et $b$ est l'entier $m$ apparaissant dans l'énoncé du théorème 3.

Notation 1   Le plus petit multiple commun de $a$ et $b$ sera noté $\mathrm{ppcm}(a,b)$.

Définition 4   Le plus grand commun diviseur de deux entiers $a$ et $b$ est l'entier $d$ apparaissant dans l'énoncé du théorème 4.

Notation 2   Le plus grand commun diviseur de $a$ et $b$ sera noté $\mathrm{pgcd}(a,b)$.

Première démonstration du théorème 3

Cette démonstration est la plus élémentaire ; elle consiste à choisir pour $m$ le multiple commun de $a$ et $b$ le plus «petit» au sens de la relation habituelle $\le$, puis à vérifier qu'il marche. La preuve est en deux parties : d'abord l'existence de $m$ (partie significative) puis son unicité (partie très facile).

Existence de $m$

Introduisons l'ensemble $A$ formé des entiers strictement positifs simultanément multiples de $a$ et de $b$. L'ensemble $A$ n'est pas vide, puisqu'il contient l'entier $ab$. Il admet donc un plus petit élément $m$. On va vérifier que cet entier $m$ convient.

Pour faire cette vérification, soit un entier $n\geqslant 1$ ; nous avons désormais à montrer une équivalence, distinguons méthodiquement les deux sens.

$\bullet$ Preuve de l'implication directe : Supposons donc que $n$ est un multiple commun de $a$ et $b$, et montrons que $n$ est un multiple de $m$. Pour ce faire, effectuons la division euclidienne de $n$ par $m$, soit $n=mq+r$, avec $0\leqslant r < m$. Comme $n$ et $m$ sont des multiples de $a$, $r=n-mq$ aussi ; de même avec $b$. Ainsi $r$ est un multiple commun de $a$ et $b$. Si $r$ était un entier strictement positif, vu l'inégalité $r<m$ il contredirait la minimalité de $m$. C'est donc que $r=0$ et donc que $n$ est un multiple de $m$.

$\bullet$ Preuve de l'implication réciproque : Supposons ici que $n$ est un multiple de $m$. Comme $m$ est lui-même multiple de $a$, $n$ est à son tour multiple de $a$ ; de même avec $b$. C'est réglé.

Unicité de $m$

Soit $m$ et $m'$ vérifiant les hypothèses du théorème. Comme $m$ est un multiple de $m$ (eh oui !), c'est un multiple commun de $a$ et $b$, donc un multiple de $m'$. De même, $m'$ est un multiple de $m$. Cela implique que $m$ et $m'$ sont forcément égaux au signe près. Comme ils sont tous deux strictement positifs, ils sont égaux. Fin de la démonstration.

Voici maintenant une première démonstration de l'existence (et l'unicité) du pgcd, qui l'obtient à partir du ppcm. Cette démonstration a le confort d'être dépourvue d'idée subtile et l'avantage de prouver le Complément 1. Elle a l'inconvénient de ne pas prouver le Complément 2 et de ne pas fournir une méthode rapide de calcul du pgcd.

Première démonstration du théorème 4

Existence de $d$

On note $m$ le ppcm de $a$ et $b$ et on pose $d=ab/m$. Remarquons que ce nombre $d$ est bien un entier : en effet, $ab$ étant un multiple commun évident de $a$ et $b$, c'est un multiple de leur ppcm. Reste à prouver qu'il convient.

Pour faire cette vérification, soit $n\geqslant 1$ un entier ; nous avons désormais à montrer une équivalence, distinguons méthodiquement les deux sens.

$\bullet$ Preuve de l'implication directe : supposons que $n$ est un diviseur commun de $a$ et $b$. On peut donc introduire deux entiers $k$ et $\ell$ tels que $a=kn$ et $b=\ell n$. Pour travailler sur ce sur quoi nous avons des informations, à savoir les multiples de $a$ et $b$, introduisons le nombre $n'=ab/n$. Ce nombre $n'$ vaut aussi $(a/n)b=kb$ et $(b/n)a=\ell a$. C'est donc un entier, et même un multiple commun de $a$ et $b$. C'est donc un multiple de $m$. Il existe donc un entier $c$ tel que $n'=cm$, soit $ab/n=c ab/d$, donc $d=cn$. On a bien prouvé que $n$ divise $d$.

$\bullet$ Preuve de l'implication réciproque : puisque $a=d (m/b)$ où $m/b$ est un entier, $d$ divise $a$ ; symétriquement puisque $b=d (m/a)$, $d$ divise $b$. Supposons maintenant que $n$ divise $d$. On voit alors aussitôt que $n$ divise $a$ et $b$.

Unicité de $d$

C'est exactement le même principe que pour le ppcm, on laisse donc cette partie de la démonstration en exercice (très) facile.

Preuve du Complément 1 : Il tombe immédiatement au vu de la formule qui donne $d$ à partir de $m$. Fin de la démonstration.

Comme promis, voici maintenant une deuxième démonstration du théorème 4, très différente dans son esprit, et qui permet pour guère plus cher de montrer simultanément le Complément 2.

Deuxième démonstration du théorème 4

La démonstration est une récurrence sur $b$ ; techniquement, on gagne sérieusement en confort si on autorise $b$ à être nul, ce que l'on n'a pas fait, volontairement, en énonçant le théorème dans l'espoir qu'il soit plus clair. On montrera donc légèrement mieux que l'énoncé de la page précédente, puisqu'on prouvera le résultat sous l'hypothèse « $a\geqslant 1$ et $b\geqslant 0$».

Avant de se lancer dans la récurrence proprement dite, on va donner un «résumé de la preuve» sous forme de programme informatique récursif.

Début du programme

* $\mathrm{pgcd}(a,0)=a$.

* Soit $r$ le reste de la division euclidienne de $a$ par $b$.
Les diviseurs communs de $a$ et $b$ sont les diviseurs communs de $b$ et $r$.
D'où : $\mathrm{pgcd}(a,b)=\mathrm{pgcd}(b,r)$.

Fin du programme

Ce résumé de démonstration convaincra peut-être les esprits les plus agiles, mais à notre niveau d'entraînement, il est plus prudent de faire ce qui est derrière les formulations récursives : une bonne vieille récurrence.

On va démontrer par «récurrence forte» sur $b\geqslant 0$ l'hypothèse $(H_b)$ suivante :

$(H_{b})$ Pour tout entier $a\geqslant 1$, il existe deux entiers (relatifs) $s$ et $t$ tels que, pour tout $n\geqslant 1$, $n$ divise $a$ et $b$ si et seulement si $n$ divise $sa+tb$.

Vérifions $(H_0)$.

Soit $a$ un entier avec $a\geqslant 1$ ; tout entier $n\geqslant 1$ qui divise $a$ divise aussi $b=0$ puisque $0n=0$. Pour tout $n\geqslant 1$, on a donc : $n$ divise $a$ et 0 si et seulement si $n$ divise $a$. Prenons alors $s=1$ et $t=0$. On a donc bien pour tout $n\geqslant 1$ : $n$ divise $a$ et 0 si et seulement si $n$ divise $sa+t\times 0$.

Soit $b$ un entier fixé, avec $b\geqslant 1$. Supposons la propriété $(H_c)$ vraie pour tout $c$ avec $0\leqslant c<b$ et montrons $(H_b)$.

Soit $a$ un entier avec $a\geqslant 1$. Notons $a=bq+r$ la division euclidienne de $a$ par $b$ (qu'on peut réaliser puisque $b\geqslant 1$).

Vérifions l'affirmation intermédiaire suivante : pour tout $n\geqslant 1$, $n$ est un diviseur commun de $a$ et $b$ si et seulement si $n$ est un diviseur commun de $b$ et $r$. C'est-à-dire, avec des mots peut-être plus lisibles : «les diviseurs communs de $a$ et $b$ sont les mêmes que ceux de $b$ et $r$.»

Soit $n$ un diviseur commun de $a$ et $b$, alors $n$ divise aussi $r=a-bq$ ; réciproquement soit $n$ un diviseur commun de $b$ et $r$, alors $n$ divise aussi $a=bq+r$.

L'affirmation intermédiaire est donc démontrée.

On peut alors appliquer l'hypothèse de récurrence $(H_r)$ (puisque précisément $0\leqslant r < b$) sur l'entier $b\geqslant 1$.

On en déduit qu'il existe deux entiers relatifs $s'$ et $t'$ tels que pour tout $n\geqslant 1$, $n$ divise $b$ et $r$ si et seulement si $n$ divise $s' b+t' r$.

Remarquons enfin que $s' b+t' r=s' b+t'(a-bq)=t' a+(s' -q)b$, et qu'ainsi, si on pose $s=t'$ et $t=s' - q$, on a bien prouvé que, pour tout $n\geqslant 1$, $n$ divise $a$ et $b$ si et seulement si $n$ divise $sa+tb$.

$(H_b)$ est donc démontrée.

On a donc bien prouvé $(H_b)$ pour tout $b\geqslant 0$, donc a fortiori pour tout $b\geqslant 1$, ce qui prouve le théorème 4 et son Complément 2.

En fait, il reste à prouver l'unicité de $d$, pour laquelle on renvoie à la démonstration précédente (où on écrivait qu'on la laissait en exercice).

Fin de la démonstration.

À présent, donnons un petit exemple sur des vrais nombres concrets, pour nous soulager l'esprit après tant de lettres.

Calcul du pgcd de $137$ et $24$

On fait des divisions euclidiennes successives et on écrit dans la colonne de droite les conséquences de ces divisions.

(1)	137	=	5	$\times$	24	+	17		$\mathrm{pgcd}(137,24)=\mathrm{pgcd}(24,17)$
(2)	24	=	1	$\times$	17	+	7		$\mathrm{pgcd}(24,17)=\mathrm{pgcd}(17,7)$
(3)	17	=	2	$\times$	7	+	3		$\mathrm{pgcd}(17,7)=\mathrm{pgcd}(7,3)$
(4)	7	=	2	$\times$	3	+	1		$\mathrm{pgcd}(7,3)=\mathrm{pgcd}(3,1)$
(5)	3	=	3	$\times$	1	+	0		$\mathrm{pgcd}(3,1)=\mathrm{pgcd}(1,0)=1$

Donc $\mathrm{pgcd}(137,24)=1$.

Ces calculs permettent ensuite sans mal de reconstituer une identité de Bézout.

• La dernière division avec un reste non nul est (4) qui donne $1=7-2\times3$.
• On va repêcher une expression de $3$ comme un reste dans la relation précédente, soit (3), ce qui donne $3=17-2\times7$.
• On reporte cette expression de $3$ donc $1=7-2\times(17-2\times7)$.
• On regroupe les termes en $17$ et $7$ donc $1=-2\times17+5\times7$.
• On va repêcher une expression de $7$ comme un reste dans la relation précédente, soit (2), ce qui donne $7=24-1\times17$.
• On reporte cette expression de $7$ donc $1=-2\times17+5\times(24-1\times17)$.
• On regroupe les termes en $24$ et $17$ donc $1=5\times24-7\times17$.
• On va repêcher une expression de $17$ comme un reste dans la relation précédente, soit (1), ce qui donne $17=137-5\times24$.
• On reporte cette expression de $17$ donc $1=5\times24-7\times(137-5\times24)$.
• On regroupe les termes en $137$ et $24$ donc
  $$1=-7\times137+40\times24.$$

• Et voilà !

Voici un autre exemple.

Calcul du pgcd de $141$ et $24$

Voici les divisions euclidiennes successives et leurs conséquences en termes de pgcd.

(1)	141	=	5	$\times$	24	+	21		$\mathrm{pgcd}(141,24)=\mathrm{pgcd}(24,21)$
(2)	24	=	1	$\times$	21	+	3		$\mathrm{pgcd}(24,21)=\mathrm{pgcd}(21,3)$
(3)	21	=	7	$\times$	3	+	0		$\mathrm{pgcd}(21,3)=\mathrm{pgcd}(3,0)=3$

Donc $\mathrm{pgcd}(141,24)=3$ et on vérifiera que ces calculs permettent de reconstituer l'identité de Bézout

$$-141+6\times24=3.$$

Donnons une dernière définition avant de quitter les pgcd.

Définition 5   On dit que deux entiers $a\geqslant 1$ et $b\geqslant 1$ sont premiers entre eux lorsque leur seul diviseur commun positif est $1$.

On veillera à ne pas confondre cette notion avec celle de nombre premier. (Par exemple, les calculs ci-dessus montrent que $137$ et $24$ sont premiers entre eux mais $24$ n'est pas premier.)