088. Trois théorèmes qui appellent le PGCD et le PPCM

Au du numéro 88 de l’Ecole AVOSZ :

  • Un rappel de ce que sont les PGCD et les PPCM, qui sont indispensables pour supprimer des fractions ou les simplifier.
  • Soient $a$ et $b$ deux entiers naturels différents de $0$. Vous allez voir que le produit $PGCD(a,b) \times PPCM(a,b)$ est égal au produit $ab.$ On rencontre souvent ce résultat mais sans aucune preuve, c’est ce que cet article vient préciser pour vous dans la section “un peu d’arithmétique“.
  • Peut-on se passer de l’algorithme d’Euclide pour calculer un PGCD avec des petits nombres, en utilisant les nombres premiers et les critères de divisibilité ? La réponse est oui et vous verrez comment.
  • Fin de l’article avec des prolongements.

Que signifient PGCD et PPCM ?

PGCD pour “plus grand commun diviseur”

Notez que $a$ et $b$ sont des multiples de $1$. L’ensemble des entiers naturels $n\in\N^{*}$ tels que $a$ soit un multiple de $n$ et $b$ un multiple de $n$ est non vide.

Si $a$ est un multiple d’un tel entier $n$, alors il existe un entier naturel $m$ tel que $a=nm$. $a$ étant non nul, $m$ est non nul donc $m\geq 1$ et aussitôt $a\geq n$.

L’ensemble $\{n\in\N^{*}, n\vert a\text{ et }n\vert b\}$ est une partie de $\N$ non vide et majorée.

Son plus grand élément est noté $PGCD(a,b).$

PPCM pour “plus petit commun multiple”

Notez que le produit $ab$, non nul, est à la fois un multiple de $a$ et de $b$. L’ensemble des entiers naturels $n\in\N^{*}$ qui sont des multiples de $a$ et de $b$ est non vide.

L’ensemble $\{n\in\N^{*}, a\vert n\text{ et }b\vert n\}$ est une partie de $\N$ non vide.

Son plus petit élément est noté $PPCM(a,b).$

Un peu d’arithmétique

Vous allez démontrer que $PGCD(a,b)\times PPCM(a,b) = ab.$

Pour plus de commodité notez $d = PGCD(a ,b)$ et $\mu=PPCM(a ,b).$

Partez de la définition du PPCM. Il existe deux entiers naturels $k$ et $\ell$ tels que $\mu = ak = b\ell.$ Pour pouvoir tirer quelque chose d’intéressant de cette relation, vous cherchez à appliquer le théorème de Gauss.

Sauf que $a$ et $b$ ne sont pas premiers entre eux.

Mais $d$ est un diviseur commun à $a$ et à $b$. Il existe deux entiers naturels $a’$ et $b’$ tels que $a=da’$ et $b=db’$. $a$ et $b$ étant non nuls, il en est de même de $a’$ et de $b’.$

De $ak = b\ell$ vous déduisez $da’k=db’\ell$ soit $d(a’k-b’\ell)=0$ et par intégrité de l’anneau $\Z$, $a’k-b’\ell=0$ soit $a’k=b’\ell.$

Notez $d’=PGCD(a’ ,b’).$

L’entier $d’$ est supérieur ou égal à $1$ par définition.

Il existe deux entiers naturels $a^{\prime\prime}$ et $b^{\prime\prime}$ non nuls tels que $a’ = d’a^{\prime\prime}$ et $b’=d’b^{\prime\prime}.$

Vous en déduisez que $a = dd’a^{\prime\prime}$ et $b = dd’b^{\prime\prime}$ donc $dd’$ est un diviseur commun à $a$ et à $b$.

Par définition de $d$, le produit $dd’$ est inférieur ou égal à $d$. Aussitôt $d’$ est inférieur ou égal à $1$.

Vous déduisez que $d’=1$.

Les entiers $a’$ et $b’$ sont premiers entre eux, et $a’$ est un diviseur de $b’\ell.$ Par le théorème de Gauss, $a’$ est un diviseur de $\ell.$

Il existe un entier $m$ non nul tel que $\ell = a’m.$

De $\mu = b\ell = ba’m$ vous déduisez que $ba’\geq \mu.$

Or, $ba’$ est un multiple de $b$. Comme $ba’=db’a’ = b’a$, vous déduisez que $ba’$ est un multiple de $a$. Par définition de $\mu$, vous avez $\mu \leq ba’$.

Ainsi $ba’ = \mu$. En multipliant par $d$, vous obtenez le résultat annoncé : $ab = d\mu.$

Calculez le PGCD sans utiliser l’algorithme d’Euclide

Pour fixer les idées seule la situation du PGCD de trois entiers sera traitée.

Soient $a$, $b$ et $c$ trois entiers naturels non nuls.

On définit de la même façon le PGCD de trois entiers naturels, c’est le plus grand entier supérieur ou égal à $1$ qui est un diviseur de $a$, $b$ et $c$.

Pour les petits nombres, on peut calculer le PGCD en utilisant des nombres premiers.

Soit $p$ un nombre premier. On rappelle qu’un nombre premier désigne un entier naturel non nul qui admet exactement deux diviseurs. Par conséquent, $1$ n’est pas un nombre premier.

Supposez que $p$ divise les trois entiers $a$, $b$ et $c$

Vous notez $(a’,b’,c’)\in(\N^{*})^3$ tel que $a=pa’$, $b=pb’$ et $c=pc’$.

Alors $PGCD(a, b, c)=p \times PGCD(a’,b’,c’).$

Notez $d = PGCD(a, b, c)$ et $d’=PGCD(a’, b’, c’).$

$d’$ divise $a’$ donc $pd’$ divise $pa’$ donc $pd’$ divise $a$.
Vous procédez de la même façon avec $b$ et $c$, et déduisez que $pd’$ est un diviseur commun à $a$, $b$ et $c$, ce qui montre que $pd’\leq d$.

Avant de poursuivre, montrez que $p$ divise $d$…

Pour cela considérez le $PGCD(d,p)$. Comme $p$ est premier, le PGCD précédent au $1$ ou $p$.

Supposez que $PGCD(d,p)=1$. Comme $d$ divise $a$, $d$ divise $pa’$ et par le théorème de Gauss, $d$ divise $a’$. Répétez le même raisonnement avec $b$ et $c$, vous déduisez que $d$ divise $a’$, $b’$ et $c’$ donc, par définition de $d’$, $d\leq d’$ donc $pd\leq pd’ \leq d$ et donc $p\leq 1$, contradiction avec le fait que $p$ est premier.

Il en résulte que $PGCD(d,p)=p$ et donc $p$ divise $d$.

Notez $\delta\in\N^{*}$ tel que $d = p\delta.$ Vous allez montrer que $d\leq pd’$. Comme $d$ divise $a$, $p\delta$ divise $pa’$ donc $\delta$ divise $a’$. Répétez ce raisonnement sur $b$ et $c$, vous déduisez que $\delta$ est un diviseur commun à $a’$, $b’$ et $c’$ donc $\delta\leq d’$. Multipliez par $p$, vous obtenez $d \leq pd’.$

Supposez que $p$ divise l’entier $a$ mais que $p$ ne divise pas l’entier $b$

Vous notez $a’\in\N^{*}$ tel que $a=pa’.$

Dans ce cas, le PGCD n’est pas modifié : $PGCD(a, b, c)= \times PGCD(a’,b,c).$

Notez $d=PGCD(a, b, c)$ et $\delta = PGCD(a’,b, c).$

Comme $\delta$ divise $a’$, $\delta$ divise aussi $pa’$ donc $a$.
$\delta$ est un diviseur commun à $a$, $b$ et $c$ donc $\delta\leq d.$

Dans l’autre sens, vous avez déjà $d$ qui divise $pa’$.

Considérez $PGCD(d,p)$. Si ce $PGCD$ vaut $1$, vous appliquez le théorème de Gauss et aussitôt $d$ divise $a’$, puis $b$, puis $c$ et donc $d\leq \delta$ et le résultat annoncé est démontré.

Comme $p$ est premier, la seule autre valeur possible du PGCD de $d$ et de $p$ est $p$. Supposez que $PGCD(d,p)=p.$ Dans ce cas-là, $p$ diviserait $d$. Or $d$ divise $b$, donc par transitivité $p$ diviserait $b$ ce qui est absurde. Le cas où $PGCD(d,p)=p$ est exclu et le résultat annoncé est finalisé.

Un exemple de calcul du PGCD

Pour des petits nombres, la connaissance du début de la suite des nombres premiers $2$, $3$, $5$, $7$ suffit dans la plupart des situations du collège et du lycée.

Soit à calculer $PGCD(12, 36, 50).$

$2$ divise tout le monde : $12$, $36$ et $50$.

Donc $PGCD(12, 36, 50) = 2\times $PGCD(6, 18, 25)$

$2$ divise $6$ mais pas $25$ donc $PGCD(6, 18, 25)=PGCD(3, 18, 25)$.

De la même façon, $2$ divise $18$ mais pas $3$ donc $PGCD(3, 18, 25)=PGCD(3, 9, 25).$

$3$ divise $3$ mais pas $25$, donc $PGCD(3, 9, 25)=PGCD(1, 9, 25)$

Comme le chiffre $1$ apparaît, vous déduisez que $PGCD(1,9,25)=1.$

Conclusion, $PGCD(12, 36, 50)=2.$

Prolongements

⓵ Calculez le PGCD des nombres $20$, $36$ et $38$ en vous inspirant de la méthode décrite ci-dessus.

⓶ Vrai ou faux ? $PGCD(a , b, c)\times PPCM(a ,b, c) = abc$ ?

Réagissez !

C’est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.

Partagez !

Diffusez cet article auprès de vos connaissances susceptibles d'être concernées.