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

Pour cet article :

  • Un rappel de ce que sont les PGCD et les PPCM, qui sont indispensables pour ajouter ou soustraire des fractions ou les simplifier.
  • Soient $a$ et $b$ deux entiers naturels différents de $0$. Vous allez établir le théorème selon lequel le produit $\mathrm{PGCD}(a,b) \times \mathrm{PGCD}(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 ». Dans cette section sera démontrée aussi un théorème important : si $d =\mathrm{PGCD}(a,b)$, alors les entiers $\frac{a}{d}$ et $\frac{b}{d}$ sont premiers entre eux.
  • Peut-on se passer de l’algorithme d’Euclide pour calculer un $\mathrm{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, ce qui constitue le dernier théorème de cet article.
  • Fin avec des prolongements.

Que signifient $\mathrm{PGCD}$ et $\mathrm{PPCM}$ ?

$\mathrm{PGCD}$ pour « plus grand commun diviseur »

Soient $a$ et $b$ deux entiers naturels différents de $0$. 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 $n$ est un entier naturel non nul qui divise $a$ il existe un entier naturel $m$ tel que $a=nm$. $a$ étant non nul, $m$ est non nul donc $1\leq m$ et aussitôt $n \leq nm$ donc $n\leq a.$

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

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

$\mathrm{PPCM}$ pour « plus petit commun multiple »

Soient $a$ et $b$ deux entiers naturels différents de $0$. 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é $\mathrm{PPCM}(a,b).$

Un peu d’arithmétique

Soient $a$ et $b$ deux entiers naturels différents de $0$.

Vous allez démontrer que :

\boxed{\mathrm{PGCD}(a,b)\times \mathrm{PPCM}(a,b) = ab.}

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

Partez de la définition du $\mathrm{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 forcément 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’=\mathrm{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 $\mathrm{PGCD}$ sans utiliser l’algorithme d’Euclide pour des petits nombres

Pour fixer les idées, seule la situation du $\mathrm{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 $\mathrm{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 $\mathrm{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 :

\boxed{\mathrm{PGCD}(a, b, c)=p \times\mathrm{PGCD}(a',b',c').}

En effet, notez $d =\mathrm{PGCD}(a, b, c)$ et $d’=\mathrm{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 $\mathrm{PGCD}(d,p)$. Comme $p$ est premier, le $\mathrm{PGCD}$ précédent au $1$ ou $p$.

Supposez que $\mathrm{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 $\mathrm{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 $\mathrm{PGCD}$ n’est pas modifié :

\boxed{\mathrm{PGCD}(a, b, c)=  \mathrm{PGCD}(a',b,c).}

En effet, notez $d=\mathrm{PGCD}(a, b, c)$ et $\delta = \mathrm{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 $\mathrm{PGCD}(d,p)$. Si ce $\mathrm{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 $\mathrm{PGCD}$ de $d$ et de $p$ est $p$. Supposez que $\mathrm{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ù $\mathrm{PGCD}(d,p)=p$ est exclu et le résultat annoncé est finalisé.

Un exemple de calcul du $\mathrm{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 $\mathrm{PGCD}(12, 36, 50).$

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

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

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

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

$3$ divise $3$ mais pas $25$, donc $\mathrm{PGCD}(3, 9, 25)=\mathrm{PGCD}(1, 9, 25)$

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

Conclusion : $\mathrm{PGCD}(12, 36, 50)=2.$

Prolongements

⓵ Calculez le $\mathrm{PGCD}$ des nombres $20$, $36$ et $38$ en vous inspirant de la méthode décrite ci-dessus qui n’utilise pas l’algorithme d’Euclide.

⓶ Vrai ou faux ? Quels que soient les entiers naturels non nuls $a$, $b$ et $c$, $\mathrm{PGCD}(a , b, c)\times \mathrm{PPCM}(a ,b, c) = abc$ ?

Partagez!

Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.

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.

Lisez d'autres articles!

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