Votre navigateur n'accepte pas le Javascript. La navigation sur ce site risque de ne pas fonctionner correctement.

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

Au du numéro 88 de l'[yanniswp_l_ecole] :

  • 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$ ?

Lisez d'autres articles !

Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !

Aidez-moi sur Facebook !

Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. 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 en utilisant les boutons de partage ci-dessous.