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 !